Independent set (graph theory)
In graph theory, an independent set, stable set, coclique or anticlique is a set of vertices in a graph, no two of which are adjacent. That is, it is a set [math]\displaystyle{ S }[/math] of vertices such that for every two vertices in [math]\displaystyle{ S }[/math], there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in [math]\displaystyle{ S }[/math]. A set is independent if and only if it is a clique in the graph's complement. The size of an independent set is the number of vertices it contains. Independent sets have also been called "internally stable sets", of which "stable set" is a shortening.^{[1]}
A maximal independent set is an independent set that is not a proper subset of any other independent set.
A maximum independent set is an independent set of largest possible size for a given graph [math]\displaystyle{ G }[/math]. This size is called the independence number of [math]\displaystyle{ G }[/math] and is usually denoted by [math]\displaystyle{ \alpha(G) }[/math].^{[2]} The optimization problem of finding such a set is called the maximum independent set problem. It is a strongly NPhard problem.^{[3]} As such, it is unlikely that there exists an efficient algorithm for finding a maximum independent set of a graph.
Every maximum independent set also is maximal, but the converse implication does not necessarily hold.
Properties
Covering/packingproblem pairs  



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.^{[4]} Therefore, the sum of the size of the largest independent set [math]\displaystyle{ \alpha(G) }[/math] and the size of a minimum vertex cover [math]\displaystyle{ \beta(G) }[/math] is equal to the number of vertices in the graph.
A vertex coloring of a graph [math]\displaystyle{ G }[/math] corresponds to a partition of its vertex set into independent subsets. Hence the minimal number of colors needed in a vertex coloring, the chromatic number [math]\displaystyle{ \chi(G) }[/math], is at least the quotient of the number of vertices in [math]\displaystyle{ G }[/math] and the independent number [math]\displaystyle{ \alpha(G) }[/math].
In a bipartite graph with no isolated vertices, 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
An independent set that is not a proper subset of another independent set is called maximal. Such sets are dominating sets. Every graph contains at most 3^{n/3} maximal independent sets,^{[5]} but many graphs have far fewer. The number of maximal independent sets in nvertex cycle graphs is given by the Perrin numbers, and the number of maximal independent sets in nvertex path graphs is given by the Padovan sequence.^{[6]} Therefore, both numbers are proportional to powers of 1.324718..., the plastic ratio.
Finding independent sets
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. This problem is sometimes referred to as "vertex packing".
 In the maximumweight 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 NPcompleteness to problems related to independent sets.
Maximum independent sets and maximum cliques
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 independent set decision problem is NPcomplete, and hence it is not believed that there is an efficient algorithm for solving it.
 The maximum independent set problem is NPhard and it is also hard to approximate.
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;^{[7]} however, for the same classes of graphs, or even for the more restricted class of bounded degree graphs, finding the maximum independent set is MAXSNPcomplete, implying that, for some constant c (depending on the degree) it is NPhard to find an approximate solution that comes within a factor of c of the optimum.^{[8]}
Exact algorithms
The maximum independent set problem is NPhard. However, it can be solved more efficiently than the O(n^{2} 2^{n}) time that would be given by a naive brute force algorithm that examines every vertex subset and checks whether it is an independent set.
As of 2017 it can be solved in time O(1.1996^{n}) using polynomial space.^{[9]} When restricted to graphs with maximum degree 3, it can be solved in time O(1.0836^{n}).^{[10]}
For many classes of graphs, a maximum weight independent set may be found in polynomial time. Famous examples are clawfree graphs,^{[11]} P_{5}free graphs^{[12]} and perfect graphs.^{[13]} For chordal graphs, a maximum weight independent set can be found in linear time.^{[14]}
Modular decomposition is a good tool for solving the maximum weight independent set problem; the linear time algorithm on cographs is the basic example for that. Another important tool are clique separators as described by Tarjan.^{[15]}
Kőnig's theorem implies that in a bipartite graph the maximum independent set can be found in polynomial time using a bipartite matching algorithm.
Approximation algorithms
In general, the maximum independent set problem cannot be approximated to a constant factor in polynomial time (unless P = NP). In fact, Max Independent Set in general is PolyAPXcomplete, meaning it is as hard as any problem that can be approximated to a polynomial factor.^{[16]} However, there are efficient approximation algorithms for restricted classes of graphs.
In planar graphs
In planar graphs, the maximum independent set may be approximated to within any approximation ratio c < 1 in polynomial time; similar polynomialtime approximation schemes exist in any family of graphs closed under taking minors.^{[17]}
In bounded degree graphs
In bounded degree graphs, effective approximation algorithms are known with approximation ratios that are constant for a fixed value of the maximum degree; 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 Δ.^{[18]} Approximation hardness bounds for such instances were proven in (Berman Karpinski). Indeed, even Max Independent Set on 3regular 3edgecolorable graphs is APXcomplete.^{[19]}
In interval intersection graphs
An interval graph is a graph in which the nodes are 1dimensional intervals (e.g. time intervals) and there is an edge between two intervals if and only if they intersect. An independent set in an interval graph is just a set of nonoverlapping intervals. The problem of finding maximum independent sets in interval graphs has been studied, for example, in the context of job scheduling: given a set of jobs that has to be executed on a computer, find a maximum set of jobs that can be executed without interfering with each other. This problem can be solved exactly in polynomial time using earliest deadline first scheduling.
In geometric intersection graphs
A geometric intersection graph is a graph in which the nodes are geometric shapes and there is an edge between two shapes if and only if they intersect. An independent set in a geometric intersection graph is just a set of disjoint (nonoverlapping) shapes. The problem of finding maximum independent sets in geometric intersection graphs has been studied, for example, in the context of Automatic label placement: given a set of locations in a map, find a maximum set of disjoint rectangular labels near these locations.
Finding a maximum independent set in intersection graphs is still NPcomplete, but it is easier to approximate than the general maximum independent set problem. A recent survey can be found in the introduction of (Chan HarPeled).
In dclawfree graphs
A dclaw in a graph is a set of d+1 vertices, one of which (the "center") is connected to the other d vertices, but the other d vertices are not connected to each other. A dclawfree graph is a graph that does not have a dclaw subgraph. Consider the algorithm that starts with an empty set, and incrementally adds an arbitrary vertex to it as long as it is not adjacent to any existing vertex. In dclawfree graphs, every added vertex invalidates at most d1 vertices from the maximum independent set; therefore, this trivial algorithm attains a (d1)approximation algorithm for the maximum independent set. In fact, it is possible to get much better approximation ratios:
 Neuwohner^{[20]} presented a polynomial time algorithm that, for any constant ε>0, finds a (d/21/63,700,992+ε)approximation for the maximum weight independent set in a dclaw free graph.
 Cygan^{[21]} presented a quasipolynomial time algorithm that, for any ε>0, attains a (d+ε)/3 approximation.
Finding maximal independent sets
The problem of finding a maximal independent set can be solved in polynomial time by a trivial parallel greedy algorithm .^{[22]} All maximal independent sets can be found in time O(3^{n/3}) = O(1.4423^{n}).
Counting independent sets
Unsolved problem in computer science: Is there a fully polynomialtime approximation algorithm for the number of independent sets in bipartite graphs? (more unsolved problems in computer science)

The counting problem #IS asks, given an undirected graph, how many independent sets it contains. This problem is intractable, namely, it is ♯Pcomplete, already on graphs with maximal degree three.^{[23]} It is further known that, assuming that NP is different from RP, the problem cannot be tractably approximated in the sense that it does not have a fully polynomialtime approximation scheme with randomization (FPRAS), even on graphs with maximal degree six;^{[24]} however it does have an fully polynomialtime approximation scheme (FPTAS) in the case where the maximal degree is five.^{[25]} The problem #BIS, of counting independent sets on bipartite graphs, is also ♯Pcomplete, already on graphs with maximal degree three.^{[26]} It is not known whether #BIS admits a FPRAS.^{[27]}
The question of counting maximal independent sets has also been studied.
Applications
The maximum independent set and its complement, the minimum vertex cover problem, is involved in proving the computational complexity of many theoretical problems.^{[28]} They also serve as useful models for real world optimization problems, for example maximum independent set is a useful model for discovering stable genetic components for designing engineered genetic systems.^{[29]}
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
 ↑ (Korshunov 1974)
 ↑ (Godsil Royle), p. 3.
 ↑ Garey, M. R.; Johnson, D. S. (19780701). ""Strong" NPCompleteness Results: Motivation, Examples, and Implications". Journal of the ACM 25 (3): 499–508. doi:10.1145/322077.322090. ISSN 00045411.
 ↑ Proof: A set V of vertices is an independent set. if and only if every edge in the graph is adjacent to at most one member of V, if and only if every edge in the graph is adjacent to at least one member not in V, if and only if the complement of V is a vertex cover.
 ↑ (Moon Moser).
 ↑ (Füredi 1987).
 ↑ (Chiba Nishizeki).
 ↑ (Berman Fujito).
 ↑ (Xiao Nagamochi)
 ↑ (Xiao Nagamochi)
 ↑ (Minty 1980),(Sbihi 1980),(Nakamura Tamura),(Faenza Oriolo),(Nobili Sassano)
 ↑ (Lokshtanov Vatshelle)
 ↑ (Grötschel Lovász)
 ↑ (Frank 1976)
 ↑ (Tarjan 1985)
 ↑ Bazgan, Cristina; Escoffier, Bruno; Paschos, Vangelis Th. (2005). "Completeness in standard and differential approximation classes: Poly(D)APX and (D)PTAScompleteness". Theoretical Computer Science 339 (2–3): 272–292. doi:10.1016/j.tcs.2005.03.007. https://basepub.dauphine.fr/handle/123456789/3724.
 ↑ (Baker 1994); (Grohe 2003).
 ↑ (Halldórsson Radhakrishnan).
 ↑ Chlebík, Miroslav; Chlebíková, Janka (2003). "Approximation Hardness for Small Occurrence Instances of NPHard Problems". Algorithms and Complexity. Lecture Notes in Computer Science. 2653. 152–164. doi:10.1007/3540448497_21. ISBN 9783540401766. https://researchportal.port.ac.uk/portal/en/publications/approximationhardnessforsmalloccurrenceinstancesofnphardproblems(fe0d8e3c740b4b8499624a0b05cc6f6b).html.
 ↑ Neuwohner, Meike (20210607). An Improved Approximation Algorithm for the Maximum Weight Independent Set Problem in dClaw Free Graphs.
 ↑ Cygan, Marek (October 2013). "Improved Approximation for 3Dimensional Matching via Bounded Pathwidth Local Search". 2013 IEEE 54th Annual Symposium on Foundations of Computer Science. pp. 509–518. doi:10.1109/FOCS.2013.61. ISBN 9780769551357. https://ieeexplore.ieee.org/document/6686187.
 ↑ (Luby 1986).
 ↑ Dyer, Martin; Greenhill, Catherine (20000401). "On Markov Chains for Independent Sets". Journal of Algorithms 35 (1): 17–49. doi:10.1006/jagm.1999.1071. ISSN 01966774. https://www.sciencedirect.com/science/article/pii/S0196677499910714.
 ↑ Sly, Allan (2010). "Computational Transition at the Uniqueness Threshold". 2010 IEEE 51st Annual Symposium on Foundations of Computer Science. pp. 287–296. doi:10.1109/FOCS.2010.34. ISBN 9781424485253. https://ieeexplore.ieee.org/document/5671190.
 ↑ Bezáková, Ivona; Galanis, Andreas; Goldberg, Leslie Ann; Guo, Heng; Štefankovič, Daniel (2019). "Approximation via Correlation Decay When Strong Spatial Mixing Fails" (in en). SIAM Journal on Computing 48 (2): 279–349. doi:10.1137/16M1083906. ISSN 00975397. https://epubs.siam.org/doi/10.1137/16M1083906.
 ↑ Xia, Mingji; Zhang, Peng; Zhao, Wenbo (20070924). "Computational complexity of counting problems on 3regular planar graphs". Theoretical Computer Science. Theory and Applications of Models of Computation 384 (1): 111–125. doi:10.1016/j.tcs.2007.05.023. ISSN 03043975. https://www.sciencedirect.com/science/article/pii/S0304397507004653., quoted in Curticapean, Radu; Dell, Holger; Fomin, Fedor; Goldberg, Leslie Ann; Lapinskas, John (20191001). "A FixedParameter Perspective on #BIS" (in en). Algorithmica 81 (10): 3844–3864. doi:10.1007/s00453019006064. ISSN 14320541.
 ↑ Cannon, Sarah; Perkins, Will (2020). Chawla, Shuchi. ed (in en). Proceedings of the Fourteenth Annual ACMSIAM Symposium on Discrete Algorithms. Philadelphia, PA: Society for Industrial and Applied Mathematics. doi:10.1137/1.9781611975994.88. ISBN 9781611975994. https://epubs.siam.org/doi/book/10.1137/1.9781611975994.
 ↑ Skiena, Steven S. (2012). The algorithm design manual. Springer. ISBN 9781848000698. OCLC 820425142.
 ↑ Hossain, Ayaan; Lopez, Eriberto; Halper, Sean M.; Cetnar, Daniel P.; Reis, Alexander C.; Strickland, Devin; Klavins, Eric; Salis, Howard M. (20200713). "Automated design of thousands of nonrepetitive parts for engineering stable genetic systems" (in en). Nature Biotechnology 38 (12): 1466–1475. doi:10.1038/s4158702005842. ISSN 15461696. PMID 32661437. https://www.nature.com/articles/s4158702005842.
References
 Baker, Brenda S. (1994), "Approximation algorithms for NPcomplete 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", Algorithms and Data Structures, Lecture Notes in Computer Science, 955, SpringerVerlag, pp. 449–460, doi:10.1007/3540602208_84, ISBN 9783540602200.
 Berman, Piotr; Karpinski, Marek (1999), "On some tighter inapproximability results", Automata, Languages and Programming, 26th International Colloquium, ICALP'99 Prague, Lecture Notes in Computer Science, 1644, Prague: SpringerVerlag, pp. 200–209, doi:10.1007/3540485236, ISBN 9783540662242
 Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis Th.; van Rooij, Johan M. M. (2010), "A bottomup method and fast algorithms for MAX INDEPENDENT SET", Algorithm Theory  SWAT 2010, Lecture Notes in Computer Science, 6139, Berlin: Springer, pp. 62–73, doi:10.1007/9783642137310_7, ISBN 9783642137303, Bibcode: 2010LNCS.6139...62B.
 "Polynomialtime approximation schemes for packing and piercing fat objects", Journal of Algorithms 46 (2): 178–189, 2003, doi:10.1016/s01966774(02)002948.
 "Approximation algorithms for maximum independent set of pseudodisks", Discrete & Computational Geometry 48 (2): 373, 2012, doi:10.1007/s0045401294175.
 Chiba, N.; Nishizeki, T. (1985), "Arboricity and subgraph listing algorithms", SIAM Journal on Computing 14 (1): 210–223, doi:10.1137/0214017.
 Erlebach, T.; Jansen, K.; Seidel, E. (2005), "PolynomialTime Approximation Schemes for Geometric Intersection Graphs", SIAM Journal on Computing 34 (6): 1302, doi:10.1137/s0097539702402676.
 Faenza, Yuri; Oriolo, Gianpaolo; Stauffer, Gautier (2014), "Solving the Weighted Stable Set Problem in ClawFree Graphs", Journal of the ACM 61 (4): 1–41, doi:10.1145/2629600.
 Fomin, Fedor V.; Grandoni, Fabrizio; Kratsch, Dieter (2009), "A measure & conquer approach for the analysis of exact algorithms", Journal of the ACM 56 (5): 1–32, doi:10.1145/1552285.1552286, article no. 25.
 "Some polynomial algorithms for certain graphs and hypergraphs", Congressus Numerantium XV: 211–226, 1976.
 Füredi, Zoltán (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 9780387952208.
 Grohe, Martin (2003), "Local treewidth, excluded minors, and approximation algorithms", Combinatorica 23 (4): 613–632, doi:10.1007/s0049300300379.
 Halldórsson, M. M.; Radhakrishnan, J. (1997), "Greed is good: Approximating independent sets in sparse and boundeddegree graphs", Algorithmica 18 (1): 145–163, doi:10.1007/BF02523693.
 Korshunov, A.D. (1974), "Coefficient of Internal Stability" (in uk), Kibernetika 10 (1): 17–28, doi:10.1007/BF01069014.
 Lokshtanov, D.; Vatshelle, M.; Villanger, Y. (2014), "Independent sets in P_{5}free graphs in polynomial time", SODA (Symposium on Discrete Algorithms): 570–581.
 "A simple parallel algorithm for the maximal independent set problem", SIAM Journal on Computing 15 (4): 1036–1053, 1986, doi:10.1137/0215074.
 Minty, G.J. (1980), "On maximal independent sets of vertices in clawfree graphs", Journal of Combinatorial Theory, Series B 28 (3): 284–304, doi:10.1016/00958956(80)90074x.
 Moon, J.W.; Moser, Leo (1965), "On cliques in graphs", Israel Journal of Mathematics 3 (1): 23–28, doi:10.1007/BF02760024.
 Nakamura, D.; Tamura, A. (2001), "A revision of Minty's algorithm for finding a maximum weight stable set in a clawfree graph", Journal of Operations Research Society Japan 44 (2): 194–204, doi:10.15807/jorsj.44.194.
 Nobili, P.; Sassano, A. (2015), An O(n^2 log n) algorithm for the weighted stable set problem in clawfree graphs, Bibcode: 2015arXiv150105775N
 Robson, J. M. (1986), "Algorithms for maximum independent sets", Journal of Algorithms 7 (3): 425–440, doi:10.1016/01966774(86)900325.
 Sbihi, Najiba (1980), "Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoile" (in fr), Discrete Mathematics 29 (1): 53–76, doi:10.1016/0012365X(90)90287R.
 Xiao, Mingyu; Nagamochi, Hiroshi (2017), "Exact algorithms for maximum independent set", Information and Computation 255: 126–146, doi:10.1016/j.ic.2017.06.001.
 Xiao, Mingyu; Nagamochi, Hiroshi (2013), "Confining sets and avoiding bottleneck cases: A simple maximum independent set algorithm in degree3 graphs", Theoretical Computer Science 469: 92–104, doi:10.1016/j.tcs.2012.09.022.
 "Decomposition by clique separators", Discrete Mathematics 55 (2): 221–232, 1985, doi:10.1016/0012365x(85)900512.
External links
 Weisstein, Eric W.. "Maximal Independent Vertex Set". http://mathworld.wolfram.com/MaximalIndependentVertexSet.html.
 Challenging Benchmarks for Maximum Clique, Maximum Independent Set, Minimum Vertex Cover and Vertex Coloring
 Independent Set and Vertex Cover, Hanan Ayad.
Original source: https://en.wikipedia.org/wiki/Independent set (graph theory).
Read more 