Independent set

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.

A maximum independent set is the largest independent set for a given graph. The problem of finding this set is called independent set problem and is a NP-complete problem. 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.

See also

• an edge independent set is called Matching