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 I of vertices such that for every two vertices in I, there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in I. 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 vertex 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-hard optimization problem. As such, it is unlikely that there exists an efficient algorithm for finding a maximum independent set of a graph.
Contents |
| Covering-packing dualities | |
| Covering problems | Packing problems |
|---|---|
| Minimum set cover | Maximum set packing |
| Minimum vertex cover | Maximum matching |
| Minimum edge cover | Maximum independent set |
A set is independent if and only if it is a clique in the graph’s complement, so the two concepts are complementary. In fact, sufficiently large graphs with no large cliques have large independent sets, a theme that is explored in Ramsey theory.
A set is independent if and only if its complement is a vertex cover. The sum of α(G) and the size of a minimum vertex cover β(G) is the number of vertices in the graph.
In a bipartite graph, the number of vertices in a maximum independent set equals the number of edges in a minimum edge covering; this is König's theorem.
An independent set that is not the subset of another independent set is called maximal. Such sets are dominating sets. Every graph contains at most 3n/3 maximal independent sets,[2] but many graphs have far fewer. The number of maximal independent sets in n-vertex cycle graphs is given by the Perrin numbers, and the number of maximal independent sets in n-vertex path graphs is given by the Padovan sequence.[3] Therefore, both numbers are proportional to powers of 1.324718, the plastic number.
In computer science, several computational problems related to independent sets have been studied.
The first three of these problems are all important in practical applications; the independent set decision problem is not, but is necessary in order to apply the theory of NP-completeness to problems related to independent sets.
The independent set problem and the clique problem are complementary: a clique in G is an independent set in the complement graph of G and vice versa. Therefore, many computational results may be applied equally well to either problem. For example, the results related to the clique problem have the following corollaries:
The maximum independent set problem and the maximum clique problem are polynomially equivalent: one can find a maximum independent set in a graph by finding a maximum clique in its complement graph, so many authors do not carefully distinguish between the two problems. Both problems are NP-complete, so it is unlikely that they can be solved in polynomial time. Nevertheless the maximum independent set problem can be solved more efficiently than the O(n2 2n) time that would be given by a naive brute force algorithm that examines every vertex subset and checks whether it is an independent set. An algorithm of Robson (1986) solves the problem in time O(20.276n); see also Fomin, Grandoni & Kratsch (2009).
Despite the close relationship between maximum cliques and maximum independent sets in arbitrary graphs, the independent set and clique problems may be very different when restricted to special classes of graphs. For instance, for sparse graphs (graphs in which the number of edges is at most a constant times the number of vertices in any subgraph), the maximum clique has bounded size and may be found exactly in linear time;[4] however, for the same classes of graphs, or even for the more restricted class of bounded degree graphs, finding the maximum independent set is MAXSNP-complete, implying that, for some constant c (depending on the degree) it is NP-hard to find an approximate solution that comes within a factor of c of the optimum.[5] However, effective approximation algorithms are known with approximation ratios that are worse than this threshold; for instance, a greedy algorithm that forms a maximal independent set by, at each step, choosing the minimum degree vertex in the graph and removing its neighbors achieves an approximation ratio of (Δ+2)/3 on graphs with maximum degree Δ.[6]
In some classes of graphs, including claw-free graphs and perfect graphs, the maximum independent set may be found in polynomial time.[7] In planar graphs, the maximum independent set remains NP-complete to find exactly but may be approximated to within any approximation ratio c < 1 in polynomial time; similar polynomial-time approximation schemes exist in any family of graphs closed under taking minors.[8]
The problem of finding a maximal independent set can be solved in polynomial time by a trivial greedy algorithm.[9] All maximal independent sets can be found in time O(3n/3).