Independent set

From Wikipedia, the free encyclopedia

It has been suggested that this article or section be merged into Independent set problem. (Discuss)

The (unexpectedly asymmetric) set of 9 blue vertices is a maximal independent set for this graph of 24 vertices.

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 $α(G)$ .^[1] 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.