Independent set (graph theory)

In graph theory, an independent, or stable, set in a graph G, which contains vertices V, is a set of vertices V' (a subset of V) such that for every two vertices in V', there is no edge connecting the two. Or, more simply put, a set of vertices such that none of them are connected by an edge. The size of a independent set is the number of vertices it contains.

The maximum independent-set problem refers to the problem of finding the largest independent-set in any graph G. This problem is NP-complete, and as such, it is very unlikely that an efficient algorithm for finding the largest independent-set of a graph exists.

The opposite of a independent set is a clique. If we already know that the clique problem is NP-complete, then it is easy to prove, as the size of a independent set is the same as the size of the largest clique in the inverse graph.

Maximum independent set problem is not be confused with maximal independent set problem. A maximal independent set is an independent set which is not contained in any larger independent set. The problem of finding a maximal independent set is solvable in polynomial time by a very simple algorithm. This algorithm starts with an empty set V. Then it searches for a vertex v that is not connected to any vertex in V and if such v is found, adds v to V. The algorithm stops when it cannot find v not connected to any vertex in V. This results in an independent set that is not contained in any larger independent set.