independentset

An independent set in a graph is a set of vertices no two of which are adjacent. In a simple graph G = (V,E), an independent set I ⊆ V has the property that for all u,v ∈ I, {u,v} ∉ E. The size of a largest independent set is called the independence number α(G), and a maximum independent set is any independent set of that size. A related term is stable set; in many sources the two terms are used interchangeably.

Independent sets are closely related to cliques in the graph’s complement. The independent sets of G correspond to cliques in the complement graph Ĝ, so a maximum independent set in G is a maximum clique in Ĝ. The complement operation also links independence to vertex covers: the complement of an independent set is a vertex cover, and α(G) + τ(G) = |V|, where τ(G) is the size of a minimum vertex cover.

Computationally, finding a maximum independent set is NP-hard in general graphs. The decision version—given k, does G contain an independent set of size at least k?—is NP-complete. Consequently, no polynomial-time algorithm is expected for general graphs unless P = NP. Some special cases have polynomial-time solutions, notably bipartite graphs, where α(G) = |V| − β(G) and, by König’s theorem, β(G) equals the size of a maximum matching. For general graphs, researchers use fixed-parameter tractable algorithms parameterized by k, as well as various heuristic and approximation methods.

Applications of independent sets appear in scheduling to avoid conflicts, resource allocation, coding theory, and network design, as well as in social network analysis and other combinatorial optimization problems.