Independent set (graph theory)

The nine blue vertices form a maximum independent set for the Generalized Petersen graph GP(12,4).

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.

Properties

Covering-packing dualities
Covering problems	Packing problems
Minimum set cover	Maximum set packing
Minimum vertex cover	Maximum matching
Minimum edge cover	Maximum independent set

Relationship to other graph parameters

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.

Maximal independent set

Main article: Maximal independent set

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 3^n/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.

Finding independent sets

Further information: Clique problem

In computer science, several computational problems related to independent sets have been studied.

• In the maximum independent set problem, the input is an undirected graph, and the output is a maximum independent set in the graph. If there are multiple maximum independent sets, only one need be output.
• In the maximum-weight independent set problem, the input is an undirected graph with weights on its vertices and the output is an independent set with maximum total weight. The maximum independent set problem is the special case in which all weights are one.
• In the maximal independent set listing problem, the input is an undirected graph, and the output is a list of all its maximal independent sets. The maximum independent set problem may be solved using as a subroutine an algorithm for the maximal independent set listing problem, because the maximum independent set must be included among all the maximal independent sets.
• In the independent set decision problem, the input is an undirected graph and a number k, and the output is a Boolean value: true if the graph contains an independent set of size k, and false otherwise.

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 decision problem is NP-complete, and hence it is not believed that there is an efficient algorithm for solving it.
• The maximum independent set problem is NP-hard and it is also hard to approximate.

Finding maximum independent sets

Further information: Clique problem#Finding maximum cliques in arbitrary graphs

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(n² 2ⁿ) 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(2^0.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]

Finding maximal independent sets

Main article: Maximal independent set

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(3^n/3).

See also

• An independent set of edges is a set of edges of which no two have a vertex in common. It is usually called a matching.
• A vertex coloring is a partition of the vertex set into independent sets.

Notes

1. ^ Godsil & Royle (2001), p. 3.
2. ^ Moon & Moser (1965).
3. ^ Füredi (1987).
4. ^ Chiba & Nishizeki (1985).
5. ^ Berman & Fujito (1995).
6. ^ Halldórsson & Radhakrishnan (1997).
7. ^ For claw-free graphs, see Sbihi (1980). For perfect graphs, see Grötschel, Lovász & Schrijver (1988).
8. ^ Baker (1994); Grohe (2003).
9. ^ Luby (1985).

References

• Baker, Brenda S. (1994), "Approximation algorithms for NP-complete problems on planar graphs", Journal of the ACM 41 (1): 153–180, doi:10.1145/174644.174650 .
• Berman, Piotr; Fujito, Toshihiro (1995), "On approximation properties of the Independent set problem for degree 3 graphs", Workshop on Algorithms and Data Structures, Lecture Notes in Computer Science, 955, Springer-Verlag, pp. 449–460, doi:10.1007/3-540-60220-8_84 .
• Chiba, N.; Nishizeki, T. (1985), "Arboricity and subgraph listing algorithms", SIAM Journal on Computing 14 (1): 210–223, doi:10.1137/0214017 .
• Fomin, Fedor V.; Grandoni, Fabrizio; Kratsch, Dieter (2009), "A measure & conquer approach for the analysis of exact algorithms", Journal of ACM 56 (5): 1–32, doi:10.1145/1552285.1552286, article no. 25 .
• Füredi, Z. (1987), "The number of maximal independent sets in connected graphs", Journal of Graph Theory 11 (4): 463–470, doi:10.1002/jgt.3190110403 .
• Godsil, Chris; Royle, Gordon (2001), Algebraic Graph Theory, New York: Springer, ISBN 0-387-95220-9 .
• Grohe, Martin (2003), "Local tree-width, excluded minors, and approximation algorithms", Combinatorica 23 (4): 613–632, doi:10.1007/s00493-003-0037-9 .
• Grötschel, M.; Lovász, L.; Schrijver, A. (1988), "9.4 Coloring Perfect Graphs", Geometric Algorithms and Combinatorial Optimization, Algorithms and Combinatorics, 2, Springer–Verlag, pp. 296–298, ISBN 038713624X .
• Halldórsson, M. M.; Radhakrishnan, J. (1997), "Greed is good: Approximating independent sets in sparse and bounded-degree graphs", Algorithmica 18 (1): 145–163, doi:10.1007/BF02523693 .
• Luby, M. (1985), "A simple parallel algorithm for the maximal independent set problem", Proc. 17th Symposium on Theory of Computing, Association for Computing Machinery, pp. 1–10, doi:10.1145/22145.22146, http://www.cs.rpi.edu/~buschc/courses/distributed/spring2007/papers/mis.pdf .
• Moon, J. W.; Moser, Leo (1965), "On cliques in graphs", Israel Journal of Mathematics 3 (1): 23–28, doi:10.1007/BF02760024, MR0182577 .
• Robson, J. M. (1986), "Algorithms for maximum independent sets", Journal of Algorithms 7 (3): 425–440, doi:10.1016/0196-6774(86)90032-5 .
• Sbihi, Najiba (1980), "Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoile" (in French), Discrete Mathematics 29 (1): 53–76, doi:10.1016/0012-365X(90)90287-R, MR553650 .

External links

• Weisstein, Eric W., "Maximal Independent Vertex Set" from MathWorld.
• Challenging Benchmarks for Maximum Clique, Maximum Independent Set, Minimum Vertex Cover and Vertex Coloring