In graph theory, an independent set or stable set is a set of vertices in a graph no two of which are adjacent. That is, it is a set V of vertices such that for every two vertices in $V$, there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in V. The size of an independent set is the number of vertices it contains.

A maximal independent set is an independent set such that adding any other node to the set forces the set to contain an edge.

A maximum independent set is a largest independent set for a given graph $G$ and its size is denoted $alpha(G)$. The problem of finding such a set is called the maximum independent set problem and is an NP-complete problem. As such, it is very unlikely that an efficient algorithm for finding a maximum independent set of a graph exists.

The problem of deciding if a graph has an independent set of a particular size is the independent set problem. It is computationally equivalent to deciding if a graph has a clique of a particular size. This follows from the fact that if a graph has an independent set of size k, then its complement (the graph on the same vertex set, but complementary edge set) has a clique of size k. The decision version of Independent Set (and consequently, clique) is known to be NP-complete.

A maximum independent set should not be confused with a maximal independent set. 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 can be solved in polynomial time by a trivial greedy algorithm.

Notes

See also

• an edge independent set is called Matching

References

External links

• http://mathworld.wolfram.com/MaximalIndependentVertexSet.html
• Challenging Benchmarks for Maximum Clique, Maximum Independent Set, Minimum Vertex Cover and Vertex Coloring