Independent set (graph theory)

Last updated January 29, 2024

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 $S$ of vertices such that for every two vertices in $S$ , there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in $S$ . 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 maximum independent set is an independent set of largest possible size for a given graph $G$ . This size is called the independence number of $G$ and is usually denoted by $\alpha (G)$ .^[2] The optimization problem of finding such a set is called the maximum independent set problem. It is a strongly NP-hard 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

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 $\alpha (G)$ and the size of a minimum vertex cover $\beta (G)$ is equal to the number of vertices in the graph.

A vertex coloring of a graph $G$ 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 $\chi (G)$ , is at least the quotient of the number of vertices in $G$ and the independent number $\alpha (G)$ .

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 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.^[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 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.

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 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 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.^[8]

Exact algorithms

The maximum independent set problem is NP-hard. However, it 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.

As of 2017 it can be solved in time O(1.1996ⁿ) using polynomial space.^[9] When restricted to graphs with maximum degree 3, it can be solved in time O(1.0836ⁿ).^[10]

For many classes of graphs, a maximum weight independent set may be found in polynomial time. Famous examples are claw-free graphs,^[11]P₅-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 Poly-APX-complete, 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 polynomial-time 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 (1999). Indeed, even Max Independent Set on 3-regular 3-edge-colorable graphs is APX-complete.^[19]

In interval intersection graphs

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

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 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^[20] 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^[21] presented a quasi-polynomial 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ⁿ).

Counting independent sets

Unsolved problem in computer science:

Is there a fully polynomial-time 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 ♯P-complete, 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 polynomial-time approximation scheme with randomization (FPRAS), even on graphs with maximal degree six;^[24] however it does have an fully polynomial-time 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 ♯P-complete, 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]

Notes

↑ Korshunov (1974)
↑ Godsil & Royle (2001), p. 3.
↑ Garey, M. R.; Johnson, D. S. (1978-07-01). ""Strong" NP-Completeness Results: Motivation, Examples, and Implications". Journal of the ACM. 25 (3): 499–508. doi: 10.1145/322077.322090 . ISSN 0004-5411. S2CID 18371269.
↑ 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 (1965).
↑ Füredi (1987).
↑ Chiba & Nishizeki (1985).
↑ Berman & Fujito (1995).
↑ Xiao & Nagamochi (2017)
↑ Xiao & Nagamochi (2013)
↑ Minty (1980),Sbihi (1980),Nakamura & Tamura (2001),Faenza, Oriolo & Stauffer (2014),Nobili & Sassano (2015)
↑ Lokshtanov, Vatshelle & Villanger (2014)
↑ Grötschel, Lovász & Schrijver (1988)
↑ Frank (1976)
↑ Tarjan (1985)
↑ Bazgan, Cristina; Escoffier, Bruno; Paschos, Vangelis Th. (2005). "Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness". Theoretical Computer Science. 339 (2–3): 272–292. doi: 10.1016/j.tcs.2005.03.007 . S2CID 1418848.
↑ Baker (1994); Grohe (2003).
↑ Halldórsson & Radhakrishnan (1997).
↑ Chlebík, Miroslav; Chlebíková, Janka (2003). "Approximation Hardness for Small Occurrence Instances of NP-Hard Problems". Algorithms and Complexity. Lecture Notes in Computer Science. Vol. 2653. pp. 152–164. doi:10.1007/3-540-44849-7_21. ISBN 978-3-540-40176-6.{{cite book}}: |journal= ignored (help)
↑ Neuwohner, Meike (2021-06-07). "An Improved Approximation Algorithm for the Maximum Weight Independent Set Problem in d-Claw Free Graphs". arXiv: 2106.03545 .{{cite journal}}: Cite journal requires |journal= (help)
↑ Cygan, Marek (October 2013). "Improved Approximation for 3-Dimensional Matching via Bounded Pathwidth Local Search". 2013 IEEE 54th Annual Symposium on Foundations of Computer Science. pp. 509–518. arXiv: 1304.1424 . doi:10.1109/FOCS.2013.61. ISBN 978-0-7695-5135-7. S2CID 14160646.
↑ Luby (1986).
↑ Dyer, Martin; Greenhill, Catherine (2000-04-01). "On Markov Chains for Independent Sets". Journal of Algorithms. 35 (1): 17–49. doi:10.1006/jagm.1999.1071. ISSN 0196-6774.
↑ 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 978-1-4244-8525-3. S2CID 901126.
↑ Bezáková, Ivona; Galanis, Andreas; Goldberg, Leslie Ann; Guo, Heng; Štefankovič, Daniel (2019). "Approximation via Correlation Decay When Strong Spatial Mixing Fails". SIAM Journal on Computing. 48 (2): 279–349. arXiv: 1510.09193 . doi:10.1137/16M1083906. ISSN 0097-5397. S2CID 131975798.
↑ Xia, Mingji; Zhang, Peng; Zhao, Wenbo (2007-09-24). "Computational complexity of counting problems on 3-regular 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 0304-3975., quoted in Curticapean, Radu; Dell, Holger; Fomin, Fedor; Goldberg, Leslie Ann; Lapinskas, John (2019-10-01). "A Fixed-Parameter Perspective on #BIS". Algorithmica. 81 (10): 3844–3864. doi: 10.1007/s00453-019-00606-4 . hdl: 1983/ecb5c34c-d6be-44ec-97ea-080f57c5e6af . ISSN 1432-0541. S2CID 3626662.
↑ Cannon, Sarah; Perkins, Will (2020). Chawla, Shuchi (ed.). Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia, PA: Society for Industrial and Applied Mathematics. arXiv: 1906.01666 . doi:10.1137/1.9781611975994.88. ISBN 978-1-61197-599-4. S2CID 174799567.
↑ Skiena, Steven S. (2012). The algorithm design manual. Springer. ISBN 978-1-84800-069-8. OCLC 820425142.
↑ Hossain, Ayaan; Lopez, Eriberto; Halper, Sean M.; Cetnar, Daniel P.; Reis, Alexander C.; Strickland, Devin; Klavins, Eric; Salis, Howard M. (2020-07-13). "Automated design of thousands of nonrepetitive parts for engineering stable genetic systems". Nature Biotechnology. 38 (12): 1466–1475. doi:10.1038/s41587-020-0584-2. ISSN 1546-1696. PMID 32661437. S2CID 220506228.

Related Research Articles

In computer science, the clique problem is the computational problem of finding cliques in a graph. It has several different formulations depending on which cliques, and what information about the cliques, should be found. Common formulations of the clique problem include finding a maximum clique, finding a maximum weight clique in a weighted graph, listing all maximal cliques, and solving the decision problem of testing whether a graph contains a clique larger than a given size.

In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices are of the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges are of the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color.

In the mathematical area of graph theory, a clique is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent. That is, a clique of a graph $is an induced subgraph of that is complete. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs. Cliques have also been studied in computer science: the task of finding whether there is a clique of a given size in a graph is NP-complete, but despite this hardness result, many algorithms for finding cliques have been studied.$

In graph theory, a vertex cover of a graph is a set of vertices that includes at least one endpoint of every edge of the graph.

In the mathematical discipline of graph theory, a matching or independent edge set in an undirected graph is a set of edges without common vertices. In other words, a subset of the edges is a matching if each vertex appears in at most one edge of that matching. Finding a matching in a bipartite graph can be treated as a network flow problem.

<span class="mw-page-title-main">Perfect graph</span> Graph with tight clique-coloring relation

In graph theory, a perfect graph is a graph in which the chromatic number equals the size of the maximum clique, both in the graph itself and in every induced subgraph. In all graphs, the chromatic number is greater than or equal to the size of the maximum clique, but they can be far apart. A graph is perfect when these numbers are equal, and remain equal after the deletion of arbitrary subsets of vertices.

<span class="mw-page-title-main">Chordal graph</span> Graph where all long cycles have a chord

In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a chord, which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced cycle in the graph should have exactly three vertices. The chordal graphs may also be characterized as the graphs that have perfect elimination orderings, as the graphs in which each minimal separator is a clique, and as the intersection graphs of subtrees of a tree. They are sometimes also called rigid circuit graphs or triangulated graphs.

<span class="mw-page-title-main">Dominating set</span> Subset of a graphs nodes such that all other nodes link to at least one

In graph theory, a dominating set for a graph $G$ is a subset $D$ of its vertices, such that any vertex of $G$ is either in $D$ , or has a neighbor in $D$ . The domination number $γ(G)$ is the number of vertices in a smallest dominating set for $G$ .

In graph theory, a domatic partition of a graph $is a partition of into disjoint sets,,..., such that each V i is a dominating set for G . The figure on the right shows a domatic partition of a graph; here the dominating set consists of the yellow vertices, consists of the green vertices, and consists of the blue vertices.$

<span class="mw-page-title-main">Maximal independent set</span> Independent set which is not a subset of any other independent set

In graph theory, a maximal independent set (MIS) or maximal stable set is an independent set that is not a subset of any other independent set. In other words, there is no vertex outside the independent set that may join it because it is maximal with respect to the independent set property.

In the mathematical discipline of graph theory, a feedback vertex set (FVS) of a graph is a set of vertices whose removal leaves a graph without cycles. Equivalently, each FVS contains at least one vertex of any cycle in the graph. The feedback vertex set number of a graph is the size of a smallest feedback vertex set. The minimum feedback vertex set problem is an NP-complete problem; it was among the first problems shown to be NP-complete. It has wide applications in operating systems, database systems, and VLSI chip design.

In graph theory and graph algorithms, a feedback arc set or feedback edge set in a directed graph is a subset of the edges of the graph that contains at least one edge out of every cycle in the graph. Removing these edges from the graph breaks all of the cycles, producing an acyclic subgraph of the given graph, often called a directed acyclic graph. A feedback arc set with the fewest possible edges is a minimum feedback arc set and its removal leaves a maximum acyclic subgraph; weighted versions of these optimization problems are also used. If a feedback arc set is minimal, meaning that removing any edge from it produces a subset that is not a feedback arc set, then it has an additional property: reversing all of its edges, rather than removing them, produces a directed acyclic graph.

Set packing is a classical NP-complete problem in computational complexity theory and combinatorics, and was one of Karp's 21 NP-complete problems. Suppose one has a finite set S and a list of subsets of S. Then, the set packing problem asks if some k subsets in the list are pairwise disjoint.

In graph theory and theoretical computer science, a maximum common induced subgraph of two graphs G and H is a graph that is an induced subgraph of both G and H, and that has as many vertices as possible.

<span class="mw-page-title-main">Boxicity</span> Smallest dimension where a graph can be represented as an intersection graph of boxes

In graph theory, boxicity is a graph invariant, introduced by Fred S. Roberts in 1969.

In graph theory, an area of mathematics, a claw-free graph is a graph that does not have a claw as an induced subgraph.

In graph theory, a clique cover or partition into cliques of a given undirected graph is a partition of the vertices into cliques, subsets of vertices within which every two vertices are adjacent. A minimum clique cover is a clique cover that uses as few cliques as possible. The minimum $k$ for which a clique cover exists is called the clique cover number of the given graph.

In graph theory and theoretical computer science, the longest path problem is the problem of finding a simple path of maximum length in a given graph. A path is called simple if it does not have any repeated vertices; the length of a path may either be measured by its number of edges, or by the sum of the weights of its edges. In contrast to the shortest path problem, which can be solved in polynomial time in graphs without negative-weight cycles, the longest path problem is NP-hard and the decision version of the problem, which asks whether a path exists of at least some given length, is NP-complete. This means that the decision problem cannot be solved in polynomial time for arbitrary graphs unless P = NP. Stronger hardness results are also known showing that it is difficult to approximate. However, it has a linear time solution for directed acyclic graphs, which has important applications in finding the critical path in scheduling problems.

In the mathematical field of graph theory, the intersection number of a graph $is the smallest number of elements in a representation of as an intersection graph of finite sets. In such a representation, each vertex is represented as a set, and two vertices are connected by an edge whenever their sets have a common element. Equivalently, the intersection number is the smallest number of cliques needed to cover all of the edges of .$

In graph theory and computer science, a dense subgraph is a subgraph with many edges per vertex. This is formalized as follows: let $G = (V, E)$ be an undirected graph and let $S = (V S, E S)$ be a subgraph of $G$ . Then the density of $S$ is defined to be:

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 , S2CID 9706753 .
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, vol. 955, Springer-Verlag, pp. 449–460, doi:10.1007/3-540-60220-8_84, ISBN 978-3-540-60220-0 .
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, vol. 1644, Prague: Springer-Verlag, pp. 200–209, doi:10.1007/3-540-48523-6, ISBN 978-3-540-66224-2, S2CID 23288736
Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis Th.; van Rooij, Johan M. M. (2010), "A bottom-up method and fast algorithms for MAX INDEPENDENT SET", Algorithm Theory - SWAT 2010, Lecture Notes in Computer Science, vol. 6139, Berlin: Springer, pp. 62–73, Bibcode:2010LNCS.6139...62B, doi:10.1007/978-3-642-13731-0_7, ISBN 978-3-642-13730-3, MR 2678485 .
Chan, T. M. (2003), "Polynomial-time approximation schemes for packing and piercing fat objects", Journal of Algorithms, 46 (2): 178–189, CiteSeerX 10.1.1.21.5344 , doi:10.1016/s0196-6774(02)00294-8 .
Chan, T. M.; Har-Peled, S. (2012), "Approximation algorithms for maximum independent set of pseudo-disks", Discrete & Computational Geometry , 48 (2): 373, arXiv: 1103.1431 , CiteSeerX 10.1.1.219.2131 , doi: 10.1007/s00454-012-9417-5 , S2CID 38183751 .
Chiba, N.; Nishizeki, T. (1985), "Arboricity and subgraph listing algorithms", SIAM Journal on Computing , 14 (1): 210–223, doi:10.1137/0214017, S2CID 207051803 .
Erlebach, T.; Jansen, K.; Seidel, E. (2005), "Polynomial-Time 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 Claw-Free Graphs", Journal of the ACM, 61 (4): 1–41, doi:10.1145/2629600, S2CID 1995056 .
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, S2CID 1186651, article no. 25{{citation}}: CS1 maint: postscript (link).
Frank, András (1976), "Some polynomial algorithms for certain graphs and hypergraphs", Congressus Numerantium, XV: 211–226.
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 978-0-387-95220-8 .
Grohe, Martin (2003), "Local tree-width, excluded minors, and approximation algorithms", Combinatorica , 23 (4): 613–632, arXiv: math/0001128 , doi: 10.1007/s00493-003-0037-9 , S2CID 11751235 .
Grötschel, Martin; Lovász, László; Schrijver, Alexander (1993), Geometric algorithms and combinatorial optimization, Algorithms and Combinatorics, vol. 2 (2nd ed.), Springer-Verlag, Berlin, doi:10.1007/978-3-642-78240-4, ISBN 978-3-642-78242-8, MR 1261419 .
Halldórsson, M. M.; Radhakrishnan, J. (1997), "Greed is good: Approximating independent sets in sparse and bounded-degree graphs", Algorithmica , 18 (1): 145–163, CiteSeerX 10.1.1.145.4523 , doi: 10.1007/BF02523693 , S2CID 4661668 .
Korshunov, A.D. (1974), "Coefficient of Internal Stability", Kibernetika (in Ukrainian), 10 (1): 17–28, doi:10.1007/BF01069014, S2CID 120343511 .
Lokshtanov, D.; Vatshelle, M.; Villanger, Y. (2014), "Independent sets in P₅-free graphs in polynomial time", SODA (Symposium on Discrete Algorithms) : 570–581.
Luby, Michael (1986), "A simple parallel algorithm for the maximal independent set problem", SIAM Journal on Computing , 15 (4): 1036–1053, CiteSeerX 10.1.1.225.5475 , doi:10.1137/0215074, MR 0861369 .
Minty, G.J. (1980), "On maximal independent sets of vertices in claw-free graphs", Journal of Combinatorial Theory, Series B , 28 (3): 284–304, doi: 10.1016/0095-8956(80)90074-x .
Moon, J.W.; Moser, Leo (1965), "On cliques in graphs", Israel Journal of Mathematics , 3 (1): 23–28, doi:10.1007/BF02760024, MR 0182577, S2CID 9855414 .
Nakamura, D.; Tamura, A. (2001), "A revision of Minty's algorithm for finding a maximum weight stable set in a claw-free 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 claw-free graphs, arXiv: 1501.05775 , Bibcode:2015arXiv150105775N
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", Discrete Mathematics (in French), 29 (1): 53–76, doi: 10.1016/0012-365X(90)90287-R , MR 0553650 .
Xiao, Mingyu; Nagamochi, Hiroshi (2017), "Exact algorithms for maximum independent set", Information and Computation , 255: 126–146, arXiv: 1312.6260 , doi:10.1016/j.ic.2017.06.001, S2CID 1714739 .
Xiao, Mingyu; Nagamochi, Hiroshi (2013), "Confining sets and avoiding bottleneck cases: A simple maximum independent set algorithm in degree-3 graphs", Theoretical Computer Science , 469: 92–104, doi: 10.1016/j.tcs.2012.09.022 .
Tarjan, R.E. (1985), "Decomposition by clique separators", Discrete Mathematics, 55 (2): 221–232, doi: 10.1016/0012-365x(85)90051-2 .

External links

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Korshunov (1974)

[2] Godsil & Royle (2001), p. 3.

[3] Garey, M. R.; Johnson, D. S. (1978-07-01). ""Strong" NP-Completeness Results: Motivation, Examples, and Implications". Journal of the ACM. 25 (3): 499–508. doi: 10.1145/322077.322090 . ISSN 0004-5411. S2CID 18371269.

[4] 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.

[5] Moon & Moser (1965).

[6] Füredi (1987).

[7] Chiba & Nishizeki (1985).

[8] Berman & Fujito (1995).

[9] Xiao & Nagamochi (2017)

[10] Xiao & Nagamochi (2013)

[11] Minty (1980),Sbihi (1980),Nakamura & Tamura (2001),Faenza, Oriolo & Stauffer (2014),Nobili & Sassano (2015)

[12] Lokshtanov, Vatshelle & Villanger (2014)

[13] Grötschel, Lovász & Schrijver (1988)

[14] Frank (1976)

[15] Tarjan (1985)

[16] Bazgan, Cristina; Escoffier, Bruno; Paschos, Vangelis Th. (2005). "Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness". Theoretical Computer Science. 339 (2–3): 272–292. doi: 10.1016/j.tcs.2005.03.007 . S2CID 1418848.

[17] Baker (1994); Grohe (2003).

[18] Halldórsson & Radhakrishnan (1997).

[chlebik-19] Chlebík, Miroslav; Chlebíková, Janka (2003). "Approximation Hardness for Small Occurrence Instances of NP-Hard Problems". Algorithms and Complexity. Lecture Notes in Computer Science. Vol. 2653. pp. 152–164. doi:10.1007/3-540-44849-7_21. ISBN 978-3-540-40176-6.{{cite book}}: |journal= ignored (help)

[20] Neuwohner, Meike (2021-06-07). "An Improved Approximation Algorithm for the Maximum Weight Independent Set Problem in d-Claw Free Graphs". arXiv: 2106.03545 .{{cite journal}}: Cite journal requires |journal= (help)

[21] Cygan, Marek (October 2013). "Improved Approximation for 3-Dimensional Matching via Bounded Pathwidth Local Search". 2013 IEEE 54th Annual Symposium on Foundations of Computer Science. pp. 509–518. arXiv: 1304.1424 . doi:10.1109/FOCS.2013.61. ISBN 978-0-7695-5135-7. S2CID 14160646.

[22] Luby (1986).

[23] Dyer, Martin; Greenhill, Catherine (2000-04-01). "On Markov Chains for Independent Sets". Journal of Algorithms. 35 (1): 17–49. doi:10.1006/jagm.1999.1071. ISSN 0196-6774.

[24] 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 978-1-4244-8525-3. S2CID 901126.

[25] Bezáková, Ivona; Galanis, Andreas; Goldberg, Leslie Ann; Guo, Heng; Štefankovič, Daniel (2019). "Approximation via Correlation Decay When Strong Spatial Mixing Fails". SIAM Journal on Computing. 48 (2): 279–349. arXiv: 1510.09193 . doi:10.1137/16M1083906. ISSN 0097-5397. S2CID 131975798.

[26] Xia, Mingji; Zhang, Peng; Zhao, Wenbo (2007-09-24). "Computational complexity of counting problems on 3-regular 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 0304-3975., quoted in Curticapean, Radu; Dell, Holger; Fomin, Fedor; Goldberg, Leslie Ann; Lapinskas, John (2019-10-01). "A Fixed-Parameter Perspective on #BIS". Algorithmica. 81 (10): 3844–3864. doi: 10.1007/s00453-019-00606-4 . hdl: 1983/ecb5c34c-d6be-44ec-97ea-080f57c5e6af . ISSN 1432-0541. S2CID 3626662.

[27] Cannon, Sarah; Perkins, Will (2020). Chawla, Shuchi (ed.). Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia, PA: Society for Industrial and Applied Mathematics. arXiv: 1906.01666 . doi:10.1137/1.9781611975994.88. ISBN 978-1-61197-599-4. S2CID 174799567.

[28] Skiena, Steven S. (2012). The algorithm design manual. Springer. ISBN 978-1-84800-069-8. OCLC 820425142.

[29] Hossain, Ayaan; Lopez, Eriberto; Halper, Sean M.; Cetnar, Daniel P.; Reis, Alexander C.; Strickland, Devin; Klavins, Eric; Salis, Howard M. (2020-07-13). "Automated design of thousands of nonrepetitive parts for engineering stable genetic systems". Nature Biotechnology. 38 (12): 1466–1475. doi:10.1038/s41587-020-0584-2. ISSN 1546-1696. PMID 32661437. S2CID 220506228.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]