View source for Independent set (graph theory)

{{Short description|Unrelated vertices in graphs}}
[[File:Independent set graph.svg|thumb|The nine blue vertices form a maximum independent set for the [[Generalized Petersen graph]] GP(12,4).]]
In [[graph theory]], an '''independent set''', '''stable set''', '''coclique''' or '''anticlique''' is a set of [[vertex (graph theory)|vertices]] in a [[Graph (discrete mathematics)|graph]], no two of which are adjacent. That is, it is a set <math>S</math> of vertices such that for every two vertices in <math>S</math>, there is no [[Edge (graph theory)|edge]] connecting the two. Equivalently, each edge in the graph has at most one endpoint in <math>S</math>. A set is independent if and only if it is a [[Clique (graph theory)|clique]] in the [[Complement graph|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.<ref>{{harvtxt|Korshunov|1974}}</ref>
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>G</math>. This size is called the '''independence number''' of ''<math>G</math>'' and is usually denoted by <math>\alpha(G)</math>.<ref>{{harvtxt|Godsil|Royle|2001}}, p. 3.</ref> The [[optimization problem]] of finding such a set is called the '''maximum independent set problem.''' It is a [[Strong NP-completeness|strongly NP-hard]] problem.<ref>{{Cite journal|last1=Garey|first1=M. R.|last2=Johnson|first2=D. S.|date=1978-07-01|title="Strong" NP-Completeness Results: Motivation, Examples, and Implications|journal=Journal of the ACM|volume=25|issue=3|pages=499–508|doi=10.1145/322077.322090|s2cid=18371269|issn=0004-5411|doi-access=free}}</ref> 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-Packing_Problem Pairs}}
===Relationship to other graph parameters===
A set is independent if and only if it is a [[Clique (graph theory)|clique]] in the graph’s [[Complement graph|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]].<ref>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.</ref> Therefore, the sum of the size of the largest independent set <math>\alpha(G)</math> and the size of a minimum vertex cover <math>\beta(G)</math> is equal to the number of vertices in the graph.
A [[Graph coloring|vertex coloring]] of a graph <math>G</math> corresponds to a [[Partition of a set|partition]] of its vertex set into independent subsets. Hence the minimal number of colors needed in a vertex coloring, the ''chromatic number''  <math>\chi(G)</math>, is at least the quotient of the number of vertices in <math>G</math> and the independent number <math>\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 (graph theory)|Kőnig's theorem]].
===Maximal independent set===
{{Main|Maximal independent set}}
An independent set that is not a proper subset of another independent set is called ''maximal''. Such sets are [[dominating set]]s. Every graph contains at most 3<sup>''n''/3</sup> maximal independent sets,<ref>{{harvtxt|Moon|Moser|1965}}.</ref> but many graphs have far fewer.
The number of maximal independent sets in ''n''-vertex [[cycle graph]]s is given by the [[Perrin number]]s, and the number of maximal independent sets in ''n''-vertex [[path graph]]s is given by the [[Padovan sequence]].<ref>{{harvtxt|Füredi|1987}}.</ref> Therefore, both numbers are proportional to powers of 1.324718..., the [[plastic ratio]].
==Finding independent sets==
{{See|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. This problem is sometimes referred to as "'''vertex packing'''".
*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 [[truth value|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.
===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 [[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 [[Approximation algorithm|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 [[dense graph|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;<ref>{{harvtxt|Chiba|Nishizeki|1985}}.</ref> however, for the same classes of graphs, or even for the more restricted class of bounded degree graphs, finding the maximum independent set is [[SNP (complexity)|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.<ref>{{harvtxt|Berman|Fujito|1995}}.</ref>
{{See|Clique problem#Finding maximum cliques in arbitrary graphs}}
=== Exact algorithms ===
The maximum independent set problem is NP-hard. However, it can be solved more efficiently than the O(''n''<sup>2</sup>&nbsp;2<sup>''n''</sup>) time that would be given by a naive [[brute-force search|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<sup>''n''</sup>) using polynomial space.<ref>{{harvtxt|Xiao|Nagamochi|2017}}</ref> When restricted to graphs with maximum degree 3, it can be solved in time O(1.0836<sup>''n''</sup>).<ref>{{harvtxt|Xiao|Nagamochi|2013}}</ref>
For many classes of graphs, a maximum weight independent set may be found in polynomial time. Famous examples are [[claw-free graph]]s,<ref>{{harvtxt|Minty|1980}},{{harvtxt|Sbihi|1980}},{{harvtxt|Nakamura|Tamura|2001}},{{harvtxt|Faenza|Oriolo|Stauffer|2014}},{{harvtxt|Nobili|Sassano|2015}}</ref> ''P''<sub>5</sub>-free graphs<ref>{{harvtxt|Lokshtanov|Vatshelle|Villanger|2014}}</ref> and [[perfect graph]]s.<ref>{{harvtxt|Grötschel|Lovász|Schrijver|1993|loc=Chapter 9: Stable Sets in Graphs}}</ref> For [[chordal graph]]s, a maximum weight independent set can be found in linear time.<ref>{{harvtxt|Frank|1976}}</ref>
[[Modular decomposition]] is a good tool for solving the maximum weight independent set problem; the linear time algorithm on [[cograph]]s is the basic example for that. Another important tool are [[clique separator]]s as described by Tarjan.<ref>{{harvtxt|Tarjan|1985}}</ref>
[[Kőnig's theorem (graph theory)|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 [[APX#Related complexity classes|Poly-APX-complete]], meaning it is as hard as any problem that can be approximated to a polynomial factor.<ref>{{cite journal|last1=Bazgan|first1=Cristina|author1-link=Cristina Bazgan|last2=Escoffier|first2=Bruno|last3=Paschos|first3=Vangelis Th.|title=Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness|journal=Theoretical Computer Science|date=2005|volume=339|issue=2–3|pages=272–292|doi=10.1016/j.tcs.2005.03.007|s2cid=1418848 |url=https://basepub.dauphine.fr/handle/123456789/3724|doi-access=free}}</ref>  However, there are efficient approximation algorithms for restricted classes of graphs.
==== In planar graphs ====
In [[planar graph]]s, the maximum independent set may be approximated to within any approximation ratio ''c''&nbsp;<&nbsp;1 in polynomial time; similar [[polynomial-time approximation scheme]]s exist in any family of graphs closed under taking [[Minor (graph theory)|minors]].<ref>{{harvtxt|Baker|1994}}; {{harvtxt|Grohe|2003}}.</ref>
==== In bounded degree graphs ====
In bounded degree graphs, effective approximation algorithms are known with [[approximation ratio]]s 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&nbsp;Δ.<ref>{{harvtxt|Halldórsson|Radhakrishnan|1997}}.</ref> Approximation hardness bounds for such instances were proven in {{harvtxt|Berman|Karpinski|1999}}. Indeed, even Max Independent Set on 3-regular 3-edge-colorable graphs is [[APX|APX-complete]].<ref name=chlebik>{{cite book|last1=Chlebík|first1=Miroslav|last2=Chlebíková|first2=Janka |chapter=Approximation Hardness for Small Occurrence Instances of NP-Hard Problems |author2-link=Janka Chlebíková|title=Proceedings of the 5th International Conference on Algorithms and Complexity|series=Lecture Notes in Computer Science |date=2003 |volume=2653 |pages=152–164 |doi=10.1007/3-540-44849-7_21|isbn=978-3-540-40176-6|chapter-url=https://researchportal.port.ac.uk/portal/en/publications/approximation-hardness-for-small-occurrence-instances-of-nphard-problems(fe0d8e3c-740b-4b84-9962-4a0b05cc6f6b).html}}</ref>
==== In interval intersection graphs ====
{{Main|Interval scheduling}}
An [[interval graph]] is a graph in which the nodes are 1-dimensional 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 non-overlapping 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 ====
{{Main|Maximum disjoint set}}
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 (non-overlapping) 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 NP-complete, but it is easier to approximate than the general maximum independent set problem. A recent survey can be found in the introduction of {{harvtxt|Chan|Har-Peled|2012}}.
==== In d-claw-free graphs ====
A ''d-claw'' 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 ''d''-[[claw-free graph]] is a graph that does not have a ''d''-claw 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 ''d''-claw-free graphs, every added vertex invalidates at most ''d''-1 vertices from the maximum independent set; therefore, this trivial algorithm attains a (''d''-1)-approximation algorithm for the maximum independent set. In fact, it is possible to get much better approximation ratios:
* Neuwohner<ref>{{Citation |last=Neuwohner |first=Meike |date=2021-06-07 |title=An Improved Approximation Algorithm for the Maximum Weight Independent Set Problem in d-Claw Free Graphs |arxiv=2106.03545 }}</ref> presented a polynomial time algorithm that, for any constant ε>0, finds a (''d''/2-1/63,700,992+ε)-approximation for the maximum weight independent set in a ''d''-claw free graph.
* Cygan<ref>{{Cite book |last=Cygan |first=Marek |title=2013 IEEE 54th Annual Symposium on Foundations of Computer Science |chapter=Improved Approximation for 3-Dimensional Matching via Bounded Pathwidth Local Search |date=October 2013 |chapter-url=https://ieeexplore.ieee.org/document/6686187 |pages=509–518 |doi=10.1109/FOCS.2013.61|arxiv=1304.1424 |isbn=978-0-7695-5135-7 |s2cid=14160646 }}</ref> presented a [[quasi-polynomial time]] algorithm that, for any ε>0, attains a (d+ε)/3 approximation.
===Finding maximal independent sets===
{{Main|Maximal independent set}}
The problem of finding a maximal independent set can be solved in [[polynomial time]] by a trivial parallel [[greedy algorithm]] .<ref>{{harvtxt|Luby|1986}}.</ref> All maximal independent sets can be found in time O(3<sup>''n''/3</sup>) = O(1.4423<sup>''n''</sup>).
=== Counting independent sets ===
{{unsolved|computer science|Is there a fully polynomial-time approximation algorithm for the number of independent sets in bipartite graphs?}}
The [[counting problem (complexity)|counting problem]] #IS asks, given an undirected graph, how many independent sets it contains. This problem is intractable, namely, it is [[♯P]]-complete, already on graphs with maximal [[degree (graph theory)|degree]] three.<ref>{{Cite journal |last1=Dyer |first1=Martin |last2=Greenhill |first2=Catherine |date=2000-04-01 |title=On Markov Chains for Independent Sets |url=https://www.sciencedirect.com/science/article/pii/S0196677499910714 |journal=Journal of Algorithms |volume=35 |issue=1 |pages=17–49 |doi=10.1006/jagm.1999.1071 |issn=0196-6774}}</ref> It is further known that, assuming that [[NP (complexity)|NP]] is different from [[RP (complexity)|RP]], the problem cannot be tractably [[Approximation algorithm|approximated]] in the sense that it does not have a fully [[polynomial-time approximation scheme]] with randomization (FPRAS), even on graphs with maximal degree six;<ref>{{Cite book |last=Sly |first=Allan |chapter=Computational Transition at the Uniqueness Threshold |date=2010 |title=2010 IEEE 51st Annual Symposium on Foundations of Computer Science |chapter-url=https://ieeexplore.ieee.org/document/5671190 |pages=287–296 |doi=10.1109/FOCS.2010.34|isbn=978-1-4244-8525-3 |s2cid=901126 }}</ref> however it does have an fully polynomial-time approximation scheme (FPTAS) in the case where the maximal degree is five.<ref>{{Cite journal |last1=Bezáková |first1=Ivona |last2=Galanis |first2=Andreas |last3=Goldberg |first3=Leslie Ann |last4=Guo |first4=Heng |last5=Štefankovič |first5=Daniel |date=2019 |title=Approximation via Correlation Decay When Strong Spatial Mixing Fails |url=https://epubs.siam.org/doi/10.1137/16M1083906 |journal=SIAM Journal on Computing |language=en |volume=48 |issue=2 |pages=279–349 |doi=10.1137/16M1083906 |s2cid=131975798 |issn=0097-5397|arxiv=1510.09193 }}</ref> The problem #BIS, of counting independent sets on [[bipartite graph]]s, is also [[♯P]]-complete, already on graphs with maximal [[degree (graph theory)|degree]] three.<ref>{{Cite journal |last1=Xia |first1=Mingji |last2=Zhang |first2=Peng |last3=Zhao |first3=Wenbo |date=2007-09-24 |title=Computational complexity of counting problems on 3-regular planar graphs |url=https://www.sciencedirect.com/science/article/pii/S0304397507004653 |journal=Theoretical Computer Science |series=Theory and Applications of Models of Computation |volume=384 |issue=1 |pages=111–125 |doi=10.1016/j.tcs.2007.05.023 |issn=0304-3975}}, quoted in {{Cite journal |last1=Curticapean |first1=Radu |last2=Dell |first2=Holger |last3=Fomin |first3=Fedor |last4=Goldberg |first4=Leslie Ann |last5=Lapinskas |first5=John |date=2019-10-01 |title=A Fixed-Parameter Perspective on #BIS |journal=Algorithmica |language=en |volume=81 |issue=10 |pages=3844–3864 |doi=10.1007/s00453-019-00606-4 |s2cid=3626662 |issn=1432-0541|doi-access=free |hdl=1983/ecb5c34c-d6be-44ec-97ea-080f57c5e6af |hdl-access=free }}</ref>
It is not known whether #BIS admits a FPRAS.<ref>{{Cite book |url=https://epubs.siam.org/doi/book/10.1137/1.9781611975994 |title=Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms |date=2020 |publisher=Society for Industrial and Applied Mathematics |isbn=978-1-61197-599-4 |editor-last=Chawla |editor-first=Shuchi |location=Philadelphia, PA |language=en |doi=10.1137/1.9781611975994.88|arxiv=1906.01666 |s2cid=174799567 |last1=Cannon |first1=Sarah |last2=Perkins |first2=Will }}</ref>
The question of [[counting maximal independent sets]] has also been studied.
== Applications ==
The maximum independent set and its complement, the [[Vertex cover|minimum vertex cover]] problem, is involved in proving the [[Computational complexity theory|computational complexity]] of many theoretical problems.<ref>{{Cite book|last=Skiena, Steven S.|title=The algorithm design manual|date=2012|publisher=Springer|isbn=978-1-84800-069-8|oclc=820425142}}</ref> They also serve as useful models for real world optimization problems, for example maximum independent set is a useful model for discovering stable [[Gene regulatory network|genetic components]] for designing [[Synthetic biology|engineered genetic systems]].<ref>{{Cite journal|last1=Hossain|first1=Ayaan|last2=Lopez|first2=Eriberto|last3=Halper|first3=Sean M.|last4=Cetnar|first4=Daniel P.|last5=Reis|first5=Alexander C.|last6=Strickland|first6=Devin|last7=Klavins|first7=Eric|last8=Salis|first8=Howard M.|date=2020-07-13|title=Automated design of thousands of nonrepetitive parts for engineering stable genetic systems|url=https://www.nature.com/articles/s41587-020-0584-2|journal=Nature Biotechnology|volume=38|issue=12|language=en|pages=1466–1475|doi=10.1038/s41587-020-0584-2|pmid=32661437|s2cid=220506228|issn=1546-1696}}</ref>
== 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 (graph theory)|matching]].
* A [[vertex coloring]] is a partition of the vertex set into independent sets.
==Notes==
{{Reflist|2}}
==References==
{{sfn whitelist|CITEREFGrötschelLovászSchrijver1993}}
{{refbegin|2}}
*{{citation|first=Brenda S.|last=Baker | author-link = Brenda Baker|title=Approximation algorithms for NP-complete problems on planar graphs|journal=[[Journal of the ACM]]|volume=41|issue=1|year=1994|pages=153–180|doi=10.1145/174644.174650|s2cid=9706753 |doi-access=free}}.
*{{citation|first1=Piotr|last1=Berman|first2=Toshihiro|last2=Fujito|title=Algorithms and Data Structures |contribution=On approximation properties of the Independent set problem for degree 3 graphs|year=1995|pages=449–460|doi=10.1007/3-540-60220-8_84|volume=955|series=Lecture Notes in Computer Science|publisher=[[Springer-Verlag]]|isbn=978-3-540-60220-0|title-link=Workshop on Algorithms and Data Structures}}.
*{{citation
| last1 = Berman | first1 = Piotr
| last2 = Karpinski | first2 = Marek
| contribution = On some tighter inapproximability results
| publisher = [[Springer-Verlag]]
| series = [[Lecture Notes in Computer Science]]
| title = Automata, Languages and Programming, 26th International Colloquium, ICALP'99 Prague
| volume = 1644
| pages = 200–209
| year = 1999
| doi = 10.1007/3-540-48523-6
| location = Prague
| isbn = 978-3-540-66224-2
| s2cid = 23288736
}}
*{{citation
| last1 = Bourgeois | first1 = Nicolas
| last2 = Escoffier | first2 = Bruno
| last3 = Paschos | first3 = Vangelis Th.
| last4 = van Rooij | first4 = Johan M. M.
| title = Algorithm Theory - SWAT 2010
| contribution = A bottom-up method and fast algorithms for MAX INDEPENDENT SET
| doi = 10.1007/978-3-642-13731-0_7
| location = Berlin
| mr = 2678485
| pages = 62–73
| publisher = Springer
| series = Lecture Notes in Computer Science
| volume = 6139
| year = 2010| isbn = 978-3-642-13730-3
| bibcode = 2010LNCS.6139...62B
| title-link = SWAT and WADS conferences
}}.
*{{Citation
| doi = 10.1016/s0196-6774(02)00294-8
| last1 = Chan | first1 = T. M. | author1-link = Timothy M. Chan
| year = 2003
| title = Polynomial-time approximation schemes for packing and piercing fat objects
| journal = Journal of Algorithms
| volume = 46
| issue = 2
| pages = 178–189
| citeseerx = 10.1.1.21.5344 }}.
*{{Citation
| last1 = Chan | first1 = T. M. | author1-link = Timothy M. Chan
| last2 = Har-Peled | first2 = S. | author2-link = Sariel Har-Peled
| doi = 10.1007/s00454-012-9417-5 | doi-access = free
| title = Approximation algorithms for maximum independent set of pseudo-disks
| journal = [[Discrete & Computational Geometry]]
| volume = 48
| issue = 2
| pages = 373
| year = 2012
| arxiv = 1103.1431| citeseerx = 10.1.1.219.2131 | s2cid = 38183751 }}.
*{{citation|first1=N.|last1=Chiba|first2=T.|last2=Nishizeki|author2-link=Takao Nishizeki|title=Arboricity and subgraph listing algorithms|journal=[[SIAM Journal on Computing]]|volume=14|issue=1|pages=210–223|year=1985|doi=10.1137/0214017|s2cid=207051803 }}.
*{{Citation
| last1 = Erlebach | first1 = T.
| last2 = Jansen | first2 = K.
| last3 = Seidel | first3 = E.
| doi = 10.1137/s0097539702402676
| title = Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
| journal = SIAM Journal on Computing
| volume = 34
| issue = 6
| pages = 1302
| year = 2005
}}.
*{{Citation
| last1 = Faenza | first1 = Yuri
| last2 = Oriolo | first2 = Gianpaolo
| last3 = Stauffer | first3 = Gautier
| title = Solving the Weighted Stable Set Problem in Claw-Free Graphs
| journal = Journal of the ACM
| volume = 61
| issue = 4
| pages = 1–41
| year = 2014
| doi=10.1145/2629600
| s2cid = 1995056
}}.
*{{citation |last1 = Fomin | first1 = Fedor V. | last2 = Grandoni | first2 = Fabrizio | last3 = Kratsch | first3 = Dieter | title = A measure & conquer approach for the analysis of exact algorithms | journal = Journal of the ACM | volume = 56 | year = 2009 |pages = 1–32 | issue = 5 | doi = 10.1145/1552285.1552286 | s2cid = 1186651 | postscript = , |id = article&nbsp;no.&nbsp;25
}}.
*{{Citation
| last = Frank | first = András | authorlink = András Frank
| title = Some polynomial algorithms for certain graphs and hypergraphs
| journal = Congressus Numerantium
| volume = XV
| pages = 211–226
| year = 1976
}}.
*{{citation | last = Füredi | first = Zoltán | author-link = Zoltán Füredi | title = The number of maximal independent sets in connected graphs | journal = [[Journal of Graph Theory]] | volume = 11 | issue = 4 | year = 1987 | pages = 463–470 | doi = 10.1002/jgt.3190110403}}.
* {{citation | last1 = Godsil | first1 = Chris | author-link1=Chris Godsil | last2 = Royle | first2 = Gordon | author-link2=Gordon Royle | title = Algebraic Graph Theory | publisher = [[Springer Science+Business Media|Springer]] | year = 2001 | location=New York | isbn = 978-0-387-95220-8}}.
*{{citation|first=Martin|last=Grohe|author-link=Martin Grohe|title=Local tree-width, excluded minors, and approximation algorithms |journal=[[Combinatorica]]|volume=23|issue=4|year=2003|doi=10.1007/s00493-003-0037-9|doi-access=free|pages=613–632|arxiv=math/0001128|s2cid=11751235}}.
*{{Cite Geometric Algorithms and Combinatorial Optimization}}. <!-- Grötschel, Lovász & Schrijver 1993 -->
*{{citation | first1 = M. M. | last1 = Halldórsson | first2 = J. | last2 = Radhakrishnan | title= Greed is good: Approximating independent sets in sparse and bounded-degree graphs | journal = [[Algorithmica]] | volume = 18 | issue = 1 | year = 1997 | pages = 145–163 | doi = 10.1007/BF02523693 | doi-access = free | citeseerx = 10.1.1.145.4523 | s2cid = 4661668 }}.
*{{citation | last = Korshunov | first = A.D. | language = uk | issue = 1 | journal = Kibernetika | pages = 17–28 | title = Coefficient of Internal Stability | volume = 10 | year = 1974 | doi=10.1007/BF01069014 | s2cid = 120343511 }}.
*{{citation
| last1 = Lokshtanov | first1 = D.
| last2 = Vatshelle | first2 = M.
| last3 = Villanger | first3 = Y.
| journal = [[SODA (Symposium on Discrete Algorithms)]]
| pages = 570–581
| title = Independent sets in ''P''<sub>5</sub>-free graphs in polynomial time
| year = 2014}}.
*{{citation
| last = Luby | first = Michael | author-link = Michael Luby
| doi = 10.1137/0215074
| issue = 4
| journal = [[SIAM Journal on Computing]]
| mr = 861369
| pages = 1036–1053
| title = A simple parallel algorithm for the maximal independent set problem
| volume = 15
| year = 1986 | citeseerx = 10.1.1.225.5475
}}.
*{{citation
| last = Minty | first = G.J.
| journal = [[Journal of Combinatorial Theory, Series B]]
| pages = 284–304
| title = On maximal independent sets of vertices in claw-free graphs
| volume = 28
| issue = 3
| year = 1980
| doi=10.1016/0095-8956(80)90074-x| doi-access = free
}}.
*{{citation | first1 = J.W. | last1 = Moon | first2 = Leo | last2 = Moser | author-link2 = Leo Moser | title = On cliques in graphs | journal = [[Israel Journal of Mathematics]] | volume = 3 | year = 1965 | issue = 1 | pages = 23–28 |mr=0182577 | doi = 10.1007/BF02760024 | doi-access= | s2cid = 9855414 }}.
*{{citation
| last1 = Nakamura | first1 = D.
| last2 = Tamura | first2 = A.
| journal = [[Journal of Operations Research Society Japan]]
| pages = 194–204
| title = A revision of Minty's algorithm for finding a maximum weight stable set in a claw-free graph
| volume = 44
| year = 2001| issue = 2
| doi = 10.15807/jorsj.44.194
| doi-access = free}}.
*{{Citation
| last1 = Nobili | first1 = P.
| last2 = Sassano | first2 = A.
| title = An O(n^2 log n) algorithm for the weighted stable set problem in claw-free graphs
| arxiv = 1501.05775
| year = 2015
| bibcode = 2015arXiv150105775N
}}
*{{citation|first=J. M.|last=Robson|title=Algorithms for maximum independent sets|journal=Journal of Algorithms|volume=7|year=1986|pages=425–440|issue=3|doi=10.1016/0196-6774(86)90032-5}}.
*{{citation | last = Sbihi | first = Najiba | author-link = Najiba Sbihi | doi = 10.1016/0012-365X(90)90287-R | language = fr | issue = 1 | journal = Discrete Mathematics | pages = 53–76 | title = Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoile | volume = 29 | year = 1980 | mr = 553650| doi-access = free }}.
*{{citation
| last1 = Xiao | first1 = Mingyu
| last2 = Nagamochi | first2 = Hiroshi
| journal = [[Information and Computation]]
| pages = 126–146
| title = Exact algorithms for maximum independent set
| volume = 255
| year = 2017
| doi = 10.1016/j.ic.2017.06.001
| arxiv = 1312.6260
| s2cid = 1714739
}}.
*{{citation
| last1 = Xiao | first1 = Mingyu
| last2 = Nagamochi | first2 = Hiroshi
| journal = [[Theoretical Computer Science]]
| pages = 92–104
| title = Confining sets and avoiding bottleneck cases: A simple maximum independent set algorithm in degree-3 graphs
| volume = 469
| year = 2013
| doi = 10.1016/j.tcs.2012.09.022
| doi-access = free}}.
*{{Citation
| last = Tarjan | first = R.E. | author-link = Robert Endre Tarjan
| title = Decomposition by clique separators
| journal = Discrete Mathematics
| volume = 55
| issue = 2 | pages = 221–232
| year = 1985
| doi=10.1016/0012-365x(85)90051-2
| doi-access = free}}.
{{refend}}
== External links ==
* {{MathWorld|urlname=MaximalIndependentVertexSet|title=Maximal Independent Vertex Set}}
* [http://www.nlsde.buaa.edu.cn/~kexu/benchmarks/graph-benchmarks.htm Challenging Benchmarks for Maximum Clique, Maximum Independent Set, Minimum Vertex Cover and Vertex Coloring] {{Webarchive|url=https://web.archive.org/web/20130529163947/http://www.nlsde.buaa.edu.cn/~kexu/benchmarks/graph-benchmarks.htm |date=2013-05-29 }}
* [http://www.hananayad.com/teaching/syde423/IndependentSet.pdf Independent Set and Vertex Cover], Hanan Ayad.
[[Category:Graph theory objects]]
[[Category:NP-complete problems]]
[[Category:Computational problems in graph theory]]