31:
767:(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; however, for the same classes of graphs, or even for the more restricted class of bounded degree graphs, finding the maximum independent set is
687:
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
960:
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
933:
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
906:
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 Δ. Approximation hardness bounds for such instances were proven in
1263:
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
1111:
with randomization (FPRAS), even on graphs with maximal degree six; however it does have an fully polynomial-time approximation scheme (FPTAS) in the case where the maximal degree is five. The problem #BIS, of counting independent sets on
762:
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
679:
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
667:
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
968:
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
2734:
1493:
938:: 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
739:
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:
1147:
of many theoretical problems. They also serve as useful models for real world optimization problems, for example maximum independent set is a useful model for discovering stable
866:, meaning it is as hard as any problem that can be approximated to a polynomial factor. However, there are efficient approximation algorithms for restricted classes of graphs.
1005:-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
142:. 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.
711:
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
862:
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
570:
429:
233:
458:
521:
365:
541:
485:
203:
178:
132:
108:
88:
2108:
Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis Th.; van Rooij, Johan M. M. (2010), "A bottom-up method and fast algorithms for MAX INDEPENDENT SET",
808:
As of 2017 it can be solved in time O(1.1996) using polynomial space. When restricted to graphs with maximum degree 3, it can be solved in time O(1.0836).
391:, 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
1938:
Hossain, Ayaan; Lopez, Eriberto; Halper, Sean M.; Cetnar, Daniel P.; Reis, Alexander C.; Strickland, Devin; Klavins, Eric; Salis, Howard M. (2020-07-13).
2876:
Xiao, Mingyu; Nagamochi, Hiroshi (2013), "Confining sets and avoiding bottleneck cases: A simple maximum independent set algorithm in degree-3 graphs",
841:
2991:
17:
2956:
1077:
358:
2034:
2332:
Fomin, Fedor V.; Grandoni, Fabrizio; Kratsch, Dieter (2009), "A measure & conquer approach for the analysis of exact algorithms",
2666:
609:. Every graph contains at most 3 maximal independent sets, but many graphs have far fewer. The number of maximal independent sets in
2529:
HalldĂłrsson, M. M.; Radhakrishnan, J. (1997), "Greed is good: Approximating independent sets in sparse and bounded-degree graphs",
2732:
Nakamura, D.; Tamura, A. (2001), "A revision of Minty's algorithm for finding a maximum weight stable set in a claw-free graph",
2610:
351:
1017:-1)-approximation algorithm for the maximum independent set. In fact, it is possible to get much better approximation ratios:
2511:
2425:
2135:
2091:
2056:
1914:
1881:
1680:
1584:
1513:
247:
problem. As such, it is unlikely that there exists an efficient algorithm for finding a maximum independent set of a graph.
2196:
2033:
Berman, Piotr; Fujito, Toshihiro (1995), "On approximation properties of the
Independent set problem for degree 3 graphs",
1108:
883:
787:
2303:
Faenza, Yuri; Oriolo, Gianpaolo; Stauffer, Gautier (2014), "Solving the
Weighted Stable Set Problem in Claw-Free Graphs",
847:
584:
2282:
Erlebach, T.; Jansen, K.; Seidel, E. (2005), "Polynomial-Time
Approximation Schemes for Geometric Intersection Graphs",
1087:#IS asks, given an undirected graph, how many independent sets it contains. This problem is intractable, namely, it is
939:
579:
with no isolated vertices, the number of vertices in a maximum independent set equals the number of edges in a minimum
2071:
1128:
2417:
811:
For many classes of graphs, a maximum weight independent set may be found in polynomial time. Famous examples are
261:
1144:
1074:
Is there a fully polynomial-time approximation algorithm for the number of independent sets in bipartite graphs?
491:
of its vertex set into independent subsets. Hence the minimal number of colors needed in a vertex coloring, the
2804:
Sbihi, Najiba (1980), "Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoile",
1164:
An independent set of edges is a set of edges of which no two have a vertex in common. It is usually called a
2986:
2981:
2695:
1084:
965:: given a set of locations in a map, find a maximum set of disjoint rectangular labels near these locations.
2954:
Challenging
Benchmarks for Maximum Clique, Maximum Independent Set, Minimum Vertex Cover and Vertex Coloring
2878:
67:
2837:
1531:
An
Improved Approximation Algorithm for the Maximum Weight Independent Set Problem in d-Claw Free Graphs
1421:"Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness"
250:
Every maximum independent set also is maximal, but the converse implication does not necessarily hold.
35:
1762:
1621:
797:
The maximum independent set problem is NP-hard. However, it can be solved more efficiently than the O(
2953:
2625:
2253:
2109:
1821:
962:
2639:
2545:
2220:
836:
is a good tool for solving the maximum weight independent set problem; the linear time algorithm on
2170:
1793:
Curticapean, Radu; Dell, Holger; Fomin, Fedor; Goldberg, Leslie Ann; Lapinskas, John (2019-10-01).
854:
the maximum independent set can be found in polynomial time using a bipartite matching algorithm.
2939:
2384:
1165:
1148:
1104:
1046:
755:
596:
301:
146:
1704:
Bezáková, Ivona; Galanis, Andreas; Goldberg, Leslie Ann; Guo, Heng; Štefankovič, Daniel (2019).
546:
405:
209:
2965:
2634:
2540:
2215:
2165:
656:
434:
244:
2493:
497:
1940:"Automated design of thousands of nonrepetitive parts for engineering stable genetic systems"
1489:
1121:
1092:
1033:
833:
384:
135:
63:
2485:
2827:
2772:
2716:
2656:
2521:
2145:
2115:
1013:-1 vertices from the maximum independent set; therefore, this trivial algorithm attains a (
951:
887:
320:
236:
1853:
8:
2901:
2835:
Xiao, Mingyu; Nagamochi, Hiroshi (2017), "Exact algorithms for maximum independent set",
2489:
924:
899:
325:
111:
2776:
2481:
2119:
1021:
Neuwohner presented a polynomial time algorithm that, for any constant ε>0, finds a (
2864:
2846:
2762:
2720:
2589:
2560:
2469:
2449:
2379:
2349:
2320:
2270:
2235:
2205:
2114:, Lecture Notes in Computer Science, vol. 6139, Berlin: Springer, pp. 62–73,
2097:
2021:
2002:
1975:
1887:
1859:
1834:
1743:
1717:
1686:
1590:
1562:
1534:
1442:
1246:
957:
802:
526:
488:
470:
188:
163:
117:
93:
73:
2179:
2156:(2003), "Polynomial-time approximation schemes for packing and piercing fat objects",
1555:"Improved Approximation for 3-Dimensional Matching via Bounded Pathwidth Local Search"
2936:
2918:
2818:
2796:
2680:
2593:
2507:
2498:, Algorithms and Combinatorics, vol. 2 (2nd ed.), Springer-Verlag, Berlin,
2421:
2274:
2131:
2087:
2066:
Berman, Piotr; Karpinski, Marek (1999), "On some tighter inapproximability results",
2052:
1979:
1967:
1959:
1920:
1910:
1891:
1877:
1826:
1782:
1747:
1735:
1676:
1641:
1580:
1509:
1238:
1152:
337:
284:
272:
114:
connecting the two. Equivalently, each edge in the graph has at most one endpoint in
2473:
2239:
2101:
1939:
1594:
1420:
1250:
878:, the maximum independent set may be approximated to within any approximation ratio
863:
601:
An independent set that is not a proper subset of another independent set is called
2913:
2887:
2868:
2856:
2813:
2792:
2743:
2724:
2704:
2675:
2664:
Minty, G.J. (1980), "On maximal independent sets of vertices in claw-free graphs",
2644:
2581:
2564:
2550:
2499:
2459:
2393:
2353:
2341:
2324:
2312:
2291:
2262:
2225:
2191:
2175:
2123:
2079:
2068:
Automata, Languages and
Programming, 26th International Colloquium, ICALP'99 Prague
2044:
2025:
2011:
1951:
1869:
1838:
1816:
1806:
1774:
1727:
1668:
1633:
1572:
1501:
1446:
1432:
1228:
1056:
903:
768:
747:, and hence it is not believed that there is an efficient algorithm for solving it.
732:
652:
630:
388:
332:
277:
139:
1690:
2960:
2823:
2759:
An O(n^2 log n) algorithm for the weighted stable set problem in claw-free graphs
2712:
2652:
2517:
2248:
2187:
2153:
2141:
2075:
2040:
1416:
1172:
1113:
1100:
1096:
1052:
998:
851:
812:
712:
576:
2362:
2194:(2012), "Approximation algorithms for maximum independent set of pseudo-disks",
2127:
1705:
2623:(1986), "A simple parallel algorithm for the maximal independent set problem",
1873:
1811:
1794:
1660:
1554:
935:
930:
805:
that examines every vertex subset and checks whether it is an independent set.
724:
646:
606:
464:
2892:
2503:
2464:
2295:
2230:
2000:(1994), "Approximation algorithms for NP-complete problems on planar graphs",
1955:
1855:
Proceedings of the
Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms
1778:
1437:
2975:
2860:
2440:
2048:
1963:
1924:
1830:
1786:
1739:
1645:
1505:
1242:
1025:/2-1/63,700,992+ε)-approximation for the maximum weight independent set in a
827:
823:
634:
618:
580:
392:
150:
2345:
1498:
Proceedings of the 5th
International Conference on Algorithms and Complexity
1066:
898:
In bounded degree graphs, effective approximation algorithms are known with
2620:
2531:
2438:(2003), "Local tree-width, excluded minors, and approximation algorithms",
2435:
2409:
2405:
2397:
1997:
1971:
1637:
1494:"Approximation Hardness for Small Occurrence Instances of NP-Hard Problems"
1140:
911:. Indeed, even Max Independent Set on 3-regular 3-edge-colorable graphs is
902:
that are constant for a fixed value of the maximum degree; for instance, a
875:
399:
308:
43:
2748:
2601:
Lokshtanov, D.; Vatshelle, M.; Villanger, Y. (2014), "Independent sets in
2083:
2016:
1763:"Computational complexity of counting problems on 3-regular planar graphs"
1233:
1217:""Strong" NP-Completeness Results: Motivation, Examples, and Implications"
1216:
2365:(1976), "Some polynomial algorithms for certain graphs and hypergraphs",
1672:
1576:
764:
744:
700:
633:. Therefore, both numbers are proportional to powers of 1.324718..., the
614:
289:
30:
2934:
2708:
2585:
2555:
1731:
1500:. Lecture Notes in Computer Science. Vol. 2653. pp. 152–164.
626:
296:
2382:(1987), "The number of maximal independent sets in connected graphs",
1706:"Approximation via Correlation Decay When Strong Spatial Mixing Fails"
1059:. All maximal independent sets can be found in time O(3) = O(1.4423).
993:
vertices, but the other d vertices are not connected to each other. A
2944:
2690:
2454:
2648:
2316:
2266:
1858:. Philadelphia, PA: Society for Industrial and Applied Mathematics.
2767:
1864:
1722:
1539:
989:+1 vertices, one of which (the "center") is connected to the other
2851:
2210:
2107:
1665:
2010 IEEE 51st Annual
Symposium on Foundations of Computer Science
1567:
1559:
2013 IEEE 54th Annual Symposium on Foundations of Computer Science
1051:
The problem of finding a maximal independent set can be solved in
2783:
Robson, J. M. (1986), "Algorithms for maximum independent sets",
837:
788:
Clique problem § Finding maximum cliques in arbitrary graphs
776:
751:
160:
is an independent set of largest possible size for a given graph
1036:
algorithm that, for any ε>0, attains a (d+ε)/3 approximation.
830:, a maximum weight independent set can be found in linear time.
402:. Therefore, the sum of the size of the largest independent set
1117:
1088:
718:
779:
to find an approximate solution that comes within a factor of
34:
The nine blue vertices form a maximum independent set for the
2572:
Korshunov, A.D. (1974), "Coefficient of Internal Stability",
2600:
1792:
1370:
1852:
Cannon, Sarah; Perkins, Will (2020). Chawla, Shuchi (ed.).
1703:
1009:-claw-free graphs, every added vertex invalidates at most
840:
is the basic example for that. Another important tool are
912:
378:
2528:
2480:
1937:
1475:
1381:
961:
graphs has been studied, for example, in the context of
934:
graphs has been studied, for example, in the context of
703:: true if the graph contains an independent set of size
523:, is at least the quotient of the number of vertices in
398:
A set is independent if and only if its complement is a
1175:
is a partition of the vertex set into independent sets.
695:
problem, the input is an undirected graph and a number
2251:(1985), "Arboricity and subgraph listing algorithms",
1661:"Computational Transition at the Uniqueness Threshold"
1415:
549:
529:
500:
473:
437:
408:
212:
191:
166:
120:
96:
76:
70:, no two of which are adjacent. That is, it is a set
2331:
2302:
2281:
2039:, Lecture Notes in Computer Science, vol. 955,
1769:. Theory and Applications of Models of Computation.
1761:
Xia, Mingji; Zhang, Peng; Zhao, Wenbo (2007-09-24).
1355:
1139:
The maximum independent set and its complement, the
1124:
three. It is not known whether #BIS admits a FPRAS.
1068:
2495:
Geometric algorithms and combinatorial optimization
1040:
945:
1419:; Escoffier, Bruno; Paschos, Vangelis Th. (2005).
918:
886:exist in any family of graphs closed under taking
564:
535:
515:
479:
452:
423:
227:
197:
172:
126:
102:
82:
1904:
1620:Dyer, Martin; Greenhill, Catherine (2000-04-01).
1487:
460:is equal to the number of vertices in the graph.
2973:
621:, and the number of maximal independent sets in
90:of vertices such that for every two vertices in
2065:
1095:three. It is further known that, assuming that
908:
659:related to independent sets have been studied.
2904:(1985), "Decomposition by clique separators",
2731:
2246:
1351:
1297:
882: < 1 in polynomial time; similar
134:. A set is independent if and only if it is a
2875:
2834:
2756:
2186:
1851:
1619:
1359:
1332:
1321:
970:
801: 2) time that would be given by a naive
359:
2735:Journal of Operations Research Society Japan
2032:
1760:
1371:Lokshtanov, Vatshelle & Villanger (2014)
1309:
1214:
1078:(more unsolved problems in computer science)
1062:
719:Maximum independent sets and maximum cliques
383:A set is independent if and only if it is a
2404:
1215:Garey, M. R.; Johnson, D. S. (1978-07-01).
1202:
1107:in the sense that it does not have a fully
893:
857:
640:
1120:-complete, already on graphs with maximal
1091:-complete, already on graphs with maximal
590:
366:
352:
2917:
2891:
2850:
2817:
2766:
2747:
2688:
2679:
2667:Journal of Combinatorial Theory, Series B
2638:
2571:
2554:
2544:
2463:
2453:
2229:
2219:
2209:
2169:
2015:
1863:
1822:1983/ecb5c34c-d6be-44ec-97ea-080f57c5e6af
1820:
1810:
1721:
1566:
1538:
1528:
1436:
1273:
1232:
1191:
715:to problems related to independent sets.
976:
743:The independent set decision problem is
29:
2611:SODA (Symposium on Discrete Algorithms)
1795:"A Fixed-Parameter Perspective on #BIS"
1622:"On Markov Chains for Independent Sets"
1481:
1382:Grötschel, Lovász & Schrijver (1993
750:The maximum independent set problem is
431:and the size of a minimum vertex cover
14:
2992:Computational problems in graph theory
2974:
2900:
2782:
2378:
1476:HalldĂłrsson & Radhakrishnan (1997)
1404:
1285:
379:Relationship to other graph parameters
2935:
2803:
2663:
2434:
2361:
2197:Discrete & Computational Geometry
1996:
1552:
1463:
1459:
1393:
1347:
1343:
884:polynomial-time approximation schemes
2619:
2152:
1607:
1356:Faenza, Oriolo & Stauffer (2014)
1143:problem, is involved in proving the
1109:polynomial-time approximation scheme
1069:Unsolved problem in computer science
723:The independent set problem and the
239:of finding such a set is called the
149:is an independent set that is not a
1658:
1384:, Chapter 9: Stable Sets in Graphs)
869:
792:
771:, implying that, for some constant
24:
2608:-free graphs in polynomial time",
1103:, the problem cannot be tractably
940:earliest deadline first scheduling
25:
3003:
2928:
2072:Lecture Notes in Computer Science
1129:counting maximal independent sets
2966:Independent Set and Vertex Cover
2940:"Maximal Independent Vertex Set"
2757:Nobili, P.; Sassano, A. (2015),
2693:(1965), "On cliques in graphs",
1041:Finding maximal independent sets
1001:is a graph that does not have a
946:In geometric intersection graphs
775:(depending on the degree) it is
241:maximum independent set problem.
1931:
1898:
1845:
1754:
1697:
1652:
1613:
1601:
1546:
1529:Neuwohner, Meike (2021-06-07),
1522:
1469:
1453:
1409:
1398:
1387:
1375:
1364:
1337:
1326:
1134:
919:In interval intersection graphs
727:are complementary: a clique in
685:maximal independent set listing
18:Maximum independent set problem
2036:Algorithms and Data Structures
1315:
1303:
1291:
1279:
1267:
1257:
1208:
1196:
1185:
677:maximum-weight independent set
559:
553:
510:
504:
447:
441:
418:
412:
262:Covering/packing-problem pairs
222:
216:
153:of any other independent set.
13:
1:
2696:Israel Journal of Mathematics
2180:10.1016/s0196-6774(02)00294-8
1989:
1553:Cygan, Marek (October 2013).
909:Berman & Karpinski (1999)
731:is an independent set in the
688:the maximal independent sets.
253:
2919:10.1016/0012-365x(85)90051-2
2879:Theoretical Computer Science
2819:10.1016/0012-365X(90)90287-R
2797:10.1016/0196-6774(86)90032-5
2681:10.1016/0095-8956(80)90074-x
2111:Algorithm Theory - SWAT 2010
1767:Theoretical Computer Science
1425:Theoretical Computer Science
1352:Nakamura & Tamura (2001)
1298:Chiba & Nishizeki (1985)
27:Unrelated vertices in graphs
7:
2838:Information and Computation
2356:, article no. 25,
2128:10.1007/978-3-642-13731-0_7
1907:The algorithm design manual
1360:Nobili & Sassano (2015)
1333:Xiao & Nagamochi (2013)
1322:Xiao & Nagamochi (2017)
1158:
971:Chan & Har-Peled (2012)
543:and the independent number
10:
3008:
2074:, vol. 1644, Prague:
1905:Skiena, Steven S. (2012).
1874:10.1137/1.9781611975994.88
1812:10.1007/s00453-019-00606-4
1310:Berman & Fujito (1995)
1153:engineered genetic systems
1044:
949:
922:
785:
644:
594:
565:{\displaystyle \alpha (G)}
424:{\displaystyle \alpha (G)}
228:{\displaystyle \alpha (G)}
206:and is usually denoted by
180:. This size is called the
36:Generalized Petersen graph
2893:10.1016/j.tcs.2012.09.022
2626:SIAM Journal on Computing
2504:10.1007/978-3-642-78240-4
2465:10.1007/s00493-003-0037-9
2296:10.1137/s0097539702402676
2284:SIAM Journal on Computing
2254:SIAM Journal on Computing
2231:10.1007/s00454-012-9417-5
1956:10.1038/s41587-020-0584-2
1779:10.1016/j.tcs.2007.05.023
1710:SIAM Journal on Computing
1438:10.1016/j.tcs.2005.03.007
1203:Godsil & Royle (2001)
1063:Counting independent sets
963:Automatic label placement
453:{\displaystyle \beta (G)}
2861:10.1016/j.ic.2017.06.001
2049:10.1007/3-540-60220-8_84
1506:10.1007/3-540-44849-7_21
1179:
1145:computational complexity
894:In bounded degree graphs
858:Approximation algorithms
844:as described by Tarjan.
693:independent set decision
641:Finding independent sets
516:{\displaystyle \chi (G)}
2385:Journal of Graph Theory
2346:10.1145/1552285.1552286
1274:Moon & Moser (1965)
1131:has also been studied.
1047:Maximal independent set
985:in a graph is a set of
754:and it is also hard to
665:maximum independent set
597:Maximal independent set
591:Maximal independent set
314:Maximum independent set
158:maximum independent set
147:maximal independent set
2414:Algebraic Graph Theory
2398:10.1002/jgt.3190110403
2367:Congressus Numerantium
1638:10.1006/jagm.1999.1071
1055:by a trivial parallel
707:, and false otherwise.
699:, and the output is a
657:computational problems
566:
537:
517:
481:
454:
425:
229:
199:
174:
128:
104:
84:
39:
2785:Journal of Algorithms
2749:10.15807/jorsj.44.194
2158:Journal of Algorithms
2084:10.1007/3-540-48523-6
2017:10.1145/174644.174650
1626:Journal of Algorithms
1234:10.1145/322077.322090
1034:quasi-polynomial time
977:In d-claw-free graphs
834:Modular decomposition
803:brute force algorithm
786:Further information:
645:Further information:
567:
538:
518:
482:
455:
426:
230:
200:
175:
129:
105:
85:
33:
2987:NP-complete problems
2982:Graph theory objects
2906:Discrete Mathematics
2806:Discrete Mathematics
2490:Schrijver, Alexander
2078:, pp. 200–209,
2043:, pp. 449–460,
1944:Nature Biotechnology
1673:10.1109/FOCS.2010.34
1667:. pp. 287–296.
1577:10.1109/FOCS.2013.61
1561:. pp. 509–518.
1141:minimum vertex cover
952:Maximum disjoint set
900:approximation ratios
547:
527:
498:
471:
435:
406:
309:Minimum vertex cover
237:optimization problem
210:
189:
164:
118:
94:
74:
2777:2015arXiv150105775N
2120:2010LNCS.6139...62B
1659:Sly, Allan (2010).
1488:ChlebĂk, Miroslav;
925:Interval scheduling
290:Maximum set packing
182:independence number
2959:2013-05-29 at the
2937:Weisstein, Eric W.
2709:10.1007/BF02760024
2586:10.1007/BF01069014
2556:10.1007/BF02523693
2334:Journal of the ACM
2305:Journal of the ACM
2003:Journal of the ACM
1732:10.1137/16M1083906
1221:Journal of the ACM
1149:genetic components
1099:is different from
1032:Cygan presented a
958:intersection graph
850:implies that in a
562:
533:
513:
477:
450:
421:
297:Minimum edge cover
225:
195:
170:
140:graph's complement
124:
100:
80:
40:
2513:978-3-642-78242-8
2482:Grötschel, Martin
2427:978-0-387-95220-8
2137:978-3-642-13730-3
2093:978-3-540-66224-2
2058:978-3-540-60220-0
1950:(12): 1466–1475.
1916:978-1-84800-069-8
1883:978-1-61197-599-4
1805:(10): 3844–3864.
1682:978-1-4244-8525-3
1586:978-0-7695-5135-7
1515:978-3-540-40176-6
1490:ChlebĂková, Janka
1029:-claw free graph.
864:Poly-APX-complete
842:clique separators
822:-free graphs and
536:{\displaystyle G}
487:corresponds to a
480:{\displaystyle G}
376:
375:
343:
342:
338:Rectangle packing
285:Minimum set cover
273:Covering problems
198:{\displaystyle G}
173:{\displaystyle G}
127:{\displaystyle S}
103:{\displaystyle S}
83:{\displaystyle S}
16:(Redirected from
2999:
2950:
2949:
2922:
2921:
2896:
2895:
2871:
2854:
2830:
2821:
2799:
2779:
2770:
2752:
2751:
2727:
2684:
2683:
2659:
2642:
2633:(4): 1036–1053,
2615:
2596:
2576:(in Ukrainian),
2567:
2558:
2548:
2524:
2476:
2467:
2457:
2430:
2400:
2374:
2357:
2327:
2298:
2277:
2242:
2233:
2223:
2213:
2182:
2173:
2148:
2104:
2061:
2028:
2019:
1998:Baker, Brenda S.
1984:
1983:
1935:
1929:
1928:
1902:
1896:
1895:
1867:
1849:
1843:
1842:
1824:
1814:
1790:
1758:
1752:
1751:
1725:
1701:
1695:
1694:
1656:
1650:
1649:
1617:
1611:
1605:
1599:
1598:
1570:
1550:
1544:
1543:
1542:
1526:
1520:
1519:
1485:
1479:
1473:
1467:
1457:
1451:
1450:
1440:
1431:(2–3): 272–292.
1417:Bazgan, Cristina
1413:
1407:
1402:
1396:
1391:
1385:
1379:
1373:
1368:
1362:
1341:
1335:
1330:
1324:
1319:
1313:
1307:
1301:
1295:
1289:
1283:
1277:
1271:
1265:
1261:
1255:
1254:
1236:
1212:
1206:
1200:
1194:
1192:Korshunov (1974)
1189:
1127:The question of
1114:bipartite graphs
1085:counting problem
1070:
1057:greedy algorithm
904:greedy algorithm
870:In planar graphs
813:claw-free graphs
793:Exact algorithms
783:of the optimum.
733:complement graph
653:computer science
631:Padovan sequence
629:is given by the
617:is given by the
605:. Such sets are
571:
569:
568:
563:
542:
540:
539:
534:
522:
520:
519:
514:
493:chromatic number
486:
484:
483:
478:
459:
457:
456:
451:
430:
428:
427:
422:
368:
361:
354:
333:Polygon covering
302:Maximum matching
278:Packing problems
269:
268:
258:
257:
245:strongly NP-hard
234:
232:
231:
226:
204:
202:
201:
196:
179:
177:
176:
171:
133:
131:
130:
125:
109:
107:
106:
101:
89:
87:
86:
81:
21:
3007:
3006:
3002:
3001:
3000:
2998:
2997:
2996:
2972:
2971:
2961:Wayback Machine
2931:
2926:
2649:10.1137/0215074
2640:10.1.1.225.5475
2607:
2546:10.1.1.145.4523
2514:
2428:
2317:10.1145/2629600
2267:10.1137/0214017
2221:10.1.1.219.2131
2138:
2094:
2076:Springer-Verlag
2059:
2041:Springer-Verlag
1992:
1987:
1936:
1932:
1917:
1903:
1899:
1884:
1850:
1846:
1759:
1755:
1702:
1698:
1683:
1657:
1653:
1618:
1614:
1606:
1602:
1587:
1551:
1547:
1527:
1523:
1516:
1486:
1482:
1474:
1470:
1458:
1454:
1414:
1410:
1403:
1399:
1392:
1388:
1380:
1376:
1369:
1365:
1342:
1338:
1331:
1327:
1320:
1316:
1308:
1304:
1296:
1292:
1284:
1280:
1272:
1268:
1262:
1258:
1213:
1209:
1201:
1197:
1190:
1186:
1182:
1173:vertex coloring
1161:
1137:
1081:
1080:
1075:
1072:
1065:
1053:polynomial time
1049:
1043:
999:claw-free graph
979:
954:
948:
927:
921:
896:
872:
860:
852:bipartite graph
848:KĹ‘nig's theorem
821:
795:
790:
769:MAXSNP-complete
721:
713:NP-completeness
649:
643:
607:dominating sets
599:
593:
585:KĹ‘nig's theorem
577:bipartite graph
548:
545:
544:
528:
525:
524:
499:
496:
495:
472:
469:
468:
465:vertex coloring
436:
433:
432:
407:
404:
403:
387:in the graph’s
381:
372:
256:
211:
208:
207:
190:
187:
186:
165:
162:
161:
119:
116:
115:
95:
92:
91:
75:
72:
71:
48:independent set
28:
23:
22:
15:
12:
11:
5:
3005:
2995:
2994:
2989:
2984:
2970:
2969:
2963:
2951:
2930:
2929:External links
2927:
2925:
2924:
2912:(2): 221–232,
2898:
2873:
2832:
2801:
2791:(3): 425–440,
2780:
2754:
2742:(2): 194–204,
2729:
2686:
2674:(3): 284–304,
2661:
2617:
2605:
2598:
2569:
2539:(1): 145–163,
2526:
2512:
2486:Lovász, László
2478:
2448:(4): 613–632,
2432:
2426:
2402:
2392:(4): 463–470,
2380:Füredi, Zoltán
2376:
2359:
2329:
2300:
2279:
2261:(1): 210–223,
2244:
2184:
2171:10.1.1.21.5344
2164:(2): 178–189,
2150:
2136:
2105:
2092:
2063:
2057:
2030:
2010:(1): 153–180,
1993:
1991:
1988:
1986:
1985:
1930:
1915:
1897:
1882:
1844:
1773:(1): 111–125.
1753:
1716:(2): 279–349.
1696:
1681:
1651:
1612:
1600:
1585:
1545:
1521:
1514:
1480:
1468:
1452:
1408:
1397:
1386:
1374:
1363:
1336:
1325:
1314:
1302:
1290:
1278:
1266:
1256:
1227:(3): 499–508.
1207:
1195:
1183:
1181:
1178:
1177:
1176:
1169:
1160:
1157:
1151:for designing
1136:
1133:
1076:
1073:
1067:
1064:
1061:
1045:Main article:
1042:
1039:
1038:
1037:
1030:
978:
975:
950:Main article:
947:
944:
936:job scheduling
931:interval graph
923:Main article:
920:
917:
895:
892:
871:
868:
859:
856:
828:chordal graphs
824:perfect graphs
819:
794:
791:
760:
759:
748:
725:clique problem
720:
717:
709:
708:
689:
681:
673:
670:vertex packing
647:Clique problem
642:
639:
619:Perrin numbers
595:Main article:
592:
589:
561:
558:
555:
552:
532:
512:
509:
506:
503:
476:
449:
446:
443:
440:
420:
417:
414:
411:
380:
377:
374:
373:
371:
370:
363:
356:
348:
345:
344:
341:
340:
335:
329:
328:
323:
317:
316:
311:
305:
304:
299:
293:
292:
287:
281:
280:
275:
265:
264:
255:
252:
224:
221:
218:
215:
194:
169:
123:
110:, there is no
99:
79:
26:
9:
6:
4:
3:
2:
3004:
2993:
2990:
2988:
2985:
2983:
2980:
2979:
2977:
2968:, Hanan Ayad.
2967:
2964:
2962:
2958:
2955:
2952:
2947:
2946:
2941:
2938:
2933:
2932:
2920:
2915:
2911:
2907:
2903:
2899:
2894:
2889:
2885:
2881:
2880:
2874:
2870:
2866:
2862:
2858:
2853:
2848:
2844:
2840:
2839:
2833:
2829:
2825:
2820:
2815:
2811:
2808:(in French),
2807:
2802:
2798:
2794:
2790:
2786:
2781:
2778:
2774:
2769:
2764:
2760:
2755:
2750:
2745:
2741:
2737:
2736:
2730:
2726:
2722:
2718:
2714:
2710:
2706:
2702:
2698:
2697:
2692:
2687:
2682:
2677:
2673:
2669:
2668:
2662:
2658:
2654:
2650:
2646:
2641:
2636:
2632:
2628:
2627:
2622:
2621:Luby, Michael
2618:
2613:
2612:
2604:
2599:
2595:
2591:
2587:
2583:
2579:
2575:
2570:
2566:
2562:
2557:
2552:
2547:
2542:
2538:
2534:
2533:
2527:
2523:
2519:
2515:
2509:
2505:
2501:
2497:
2496:
2491:
2487:
2483:
2479:
2475:
2471:
2466:
2461:
2456:
2451:
2447:
2443:
2442:
2441:Combinatorica
2437:
2436:Grohe, Martin
2433:
2429:
2423:
2419:
2415:
2411:
2410:Royle, Gordon
2407:
2406:Godsil, Chris
2403:
2399:
2395:
2391:
2387:
2386:
2381:
2377:
2372:
2368:
2364:
2363:Frank, András
2360:
2355:
2351:
2347:
2343:
2339:
2335:
2330:
2326:
2322:
2318:
2314:
2310:
2306:
2301:
2297:
2293:
2289:
2285:
2280:
2276:
2272:
2268:
2264:
2260:
2256:
2255:
2250:
2249:Nishizeki, T.
2245:
2241:
2237:
2232:
2227:
2222:
2217:
2212:
2207:
2203:
2199:
2198:
2193:
2192:Har-Peled, S.
2189:
2185:
2181:
2177:
2172:
2167:
2163:
2159:
2155:
2151:
2147:
2143:
2139:
2133:
2129:
2125:
2121:
2117:
2113:
2112:
2106:
2103:
2099:
2095:
2089:
2085:
2081:
2077:
2073:
2069:
2064:
2060:
2054:
2050:
2046:
2042:
2038:
2037:
2031:
2027:
2023:
2018:
2013:
2009:
2005:
2004:
1999:
1995:
1994:
1981:
1977:
1973:
1969:
1965:
1961:
1957:
1953:
1949:
1945:
1941:
1934:
1926:
1922:
1918:
1912:
1908:
1901:
1893:
1889:
1885:
1879:
1875:
1871:
1866:
1861:
1857:
1856:
1848:
1840:
1836:
1832:
1828:
1823:
1818:
1813:
1808:
1804:
1800:
1796:
1788:
1784:
1780:
1776:
1772:
1768:
1764:
1757:
1749:
1745:
1741:
1737:
1733:
1729:
1724:
1719:
1715:
1711:
1707:
1700:
1692:
1688:
1684:
1678:
1674:
1670:
1666:
1662:
1655:
1647:
1643:
1639:
1635:
1631:
1627:
1623:
1616:
1609:
1604:
1596:
1592:
1588:
1582:
1578:
1574:
1569:
1564:
1560:
1556:
1549:
1541:
1536:
1532:
1525:
1517:
1511:
1507:
1503:
1499:
1495:
1491:
1484:
1477:
1472:
1465:
1461:
1456:
1448:
1444:
1439:
1434:
1430:
1426:
1422:
1418:
1412:
1406:
1405:Tarjan (1985)
1401:
1395:
1390:
1383:
1378:
1372:
1367:
1361:
1357:
1353:
1349:
1345:
1340:
1334:
1329:
1323:
1318:
1311:
1306:
1299:
1294:
1287:
1286:FĂĽredi (1987)
1282:
1275:
1270:
1260:
1252:
1248:
1244:
1240:
1235:
1230:
1226:
1222:
1218:
1211:
1204:
1199:
1193:
1188:
1184:
1174:
1170:
1167:
1163:
1162:
1156:
1154:
1150:
1146:
1142:
1132:
1130:
1125:
1123:
1119:
1115:
1110:
1106:
1102:
1098:
1094:
1090:
1086:
1079:
1060:
1058:
1054:
1048:
1035:
1031:
1028:
1024:
1020:
1019:
1018:
1016:
1012:
1008:
1004:
1000:
996:
992:
988:
984:
974:
972:
966:
964:
959:
953:
943:
941:
937:
932:
926:
916:
914:
910:
905:
901:
891:
889:
885:
881:
877:
876:planar graphs
867:
865:
855:
853:
849:
845:
843:
839:
835:
831:
829:
825:
818:
814:
809:
806:
804:
800:
789:
784:
782:
778:
774:
770:
766:
765:sparse graphs
757:
753:
749:
746:
742:
741:
740:
738:
734:
730:
726:
716:
714:
706:
702:
701:Boolean value
698:
694:
690:
686:
682:
678:
674:
671:
666:
662:
661:
660:
658:
654:
648:
638:
636:
635:plastic ratio
632:
628:
624:
620:
616:
612:
608:
604:
598:
588:
586:
582:
581:edge covering
578:
573:
556:
550:
530:
507:
501:
494:
490:
474:
466:
461:
444:
438:
415:
409:
401:
396:
394:
393:Ramsey theory
390:
386:
369:
364:
362:
357:
355:
350:
349:
347:
346:
339:
336:
334:
331:
330:
327:
324:
322:
319:
318:
315:
312:
310:
307:
306:
303:
300:
298:
295:
294:
291:
288:
286:
283:
282:
279:
276:
274:
271:
270:
267:
266:
263:
260:
259:
251:
248:
246:
242:
238:
219:
213:
205:
192:
183:
167:
159:
154:
152:
151:proper subset
148:
143:
141:
137:
121:
113:
97:
77:
69:
65:
61:
57:
53:
49:
45:
37:
32:
19:
2943:
2909:
2905:
2902:Tarjan, R.E.
2883:
2877:
2842:
2836:
2812:(1): 53–76,
2809:
2805:
2788:
2784:
2758:
2739:
2733:
2703:(1): 23–28,
2700:
2694:
2689:Moon, J.W.;
2671:
2665:
2630:
2624:
2609:
2602:
2580:(1): 17–28,
2577:
2573:
2536:
2532:Algorithmica
2530:
2494:
2455:math/0001128
2445:
2439:
2416:, New York:
2413:
2389:
2383:
2370:
2366:
2337:
2333:
2308:
2304:
2287:
2283:
2258:
2252:
2201:
2195:
2161:
2157:
2110:
2067:
2035:
2007:
2001:
1947:
1943:
1933:
1909:. Springer.
1906:
1900:
1854:
1847:
1802:
1799:Algorithmica
1798:
1791:, quoted in
1770:
1766:
1756:
1713:
1709:
1699:
1664:
1654:
1632:(1): 17–49.
1629:
1625:
1615:
1603:
1558:
1548:
1530:
1524:
1497:
1483:
1471:
1464:Grohe (2003)
1460:Baker (1994)
1455:
1428:
1424:
1411:
1400:
1394:Frank (1976)
1389:
1377:
1366:
1348:Sbihi (1980)
1344:Minty (1980)
1339:
1328:
1317:
1305:
1293:
1281:
1269:
1259:
1224:
1220:
1210:
1198:
1187:
1138:
1135:Applications
1126:
1105:approximated
1082:
1050:
1026:
1022:
1014:
1010:
1006:
1002:
994:
990:
986:
982:
980:
967:
956:A geometric
955:
928:
913:APX-complete
897:
879:
873:
861:
846:
832:
816:
810:
807:
798:
796:
780:
772:
761:
736:
728:
722:
710:
704:
696:
692:
684:
676:
669:
664:
650:
622:
615:cycle graphs
610:
602:
600:
574:
492:
462:
400:vertex cover
397:
382:
321:Bin covering
313:
249:
240:
185:
181:
157:
155:
144:
62:is a set of
59:
55:
51:
47:
44:graph theory
41:
2845:: 126–146,
2574:Kibernetika
2340:(5): 1–32,
2311:(4): 1–41,
2290:(6): 1302,
2247:Chiba, N.;
2188:Chan, T. M.
2154:Chan, T. M.
1608:Luby (1986)
756:approximate
745:NP-complete
627:path graphs
467:of a graph
326:Bin packing
2976:Categories
2886:: 92–104,
2768:1501.05775
2691:Moser, Leo
2204:(2): 373,
1990:References
1865:1906.01666
1723:1510.09193
1540:2106.03545
1116:, is also
655:, several
583:; this is
389:complement
254:Properties
60:anticlique
52:stable set
2945:MathWorld
2852:1312.6260
2635:CiteSeerX
2614:: 570–581
2594:120343511
2541:CiteSeerX
2373:: 211–226
2275:207051803
2216:CiteSeerX
2211:1103.1431
2166:CiteSeerX
1980:220506228
1964:1546-1696
1925:820425142
1892:174799567
1831:1432-0541
1787:0304-3975
1748:131975798
1740:0097-5397
1646:0196-6774
1568:1304.1424
1243:0004-5411
551:α
502:χ
489:partition
439:β
410:α
214:α
38:GP(12,4).
2957:Archived
2492:(1993),
2474:11751235
2418:Springer
2412:(2001),
2240:38183751
2102:23288736
1972:32661437
1595:14160646
1492:(2003).
1251:18371269
1166:matching
1159:See also
838:cographs
625:-vertex
613:-vertex
243:It is a
64:vertices
56:coclique
2869:1714739
2828:0553650
2773:Bibcode
2725:9855414
2717:0182577
2657:0861369
2565:4661668
2522:1261419
2354:1186651
2325:1995056
2146:2678485
2116:Bibcode
2026:9706753
1839:3626662
1447:1418848
1205:, p. 3.
777:NP-hard
752:NP-hard
691:In the
683:In the
675:In the
663:In the
603:maximal
138:in the
2867:
2826:
2723:
2715:
2655:
2637:
2592:
2563:
2543:
2520:
2510:
2472:
2424:
2352:
2323:
2273:
2238:
2218:
2168:
2144:
2134:
2100:
2090:
2055:
2024:
1978:
1970:
1962:
1923:
1913:
1890:
1880:
1837:
1829:
1785:
1746:
1738:
1691:901126
1689:
1679:
1644:
1593:
1583:
1512:
1445:
1264:cover.
1249:
1241:
1122:degree
1093:degree
983:d-claw
888:minors
826:. For
385:clique
235:. The
136:clique
2865:S2CID
2847:arXiv
2763:arXiv
2721:S2CID
2590:S2CID
2561:S2CID
2470:S2CID
2450:arXiv
2350:S2CID
2321:S2CID
2271:S2CID
2236:S2CID
2206:arXiv
2098:S2CID
2022:S2CID
1976:S2CID
1888:S2CID
1860:arXiv
1835:S2CID
1744:S2CID
1718:arXiv
1687:S2CID
1591:S2CID
1563:arXiv
1535:arXiv
1443:S2CID
1247:S2CID
1180:Notes
575:In a
68:graph
66:in a
46:, an
2508:ISBN
2422:ISBN
2132:ISBN
2088:ISBN
2053:ISBN
1968:PMID
1960:ISSN
1921:OCLC
1911:ISBN
1878:ISBN
1827:ISSN
1783:ISSN
1736:ISSN
1677:ISBN
1642:ISSN
1581:ISBN
1510:ISBN
1239:ISSN
1083:The
680:one.
112:edge
2914:doi
2888:doi
2884:469
2857:doi
2843:255
2814:doi
2793:doi
2744:doi
2705:doi
2676:doi
2645:doi
2582:doi
2551:doi
2500:doi
2460:doi
2394:doi
2342:doi
2313:doi
2292:doi
2263:doi
2226:doi
2176:doi
2124:doi
2080:doi
2045:doi
2012:doi
1952:doi
1870:doi
1817:hdl
1807:doi
1775:doi
1771:384
1728:doi
1669:doi
1634:doi
1573:doi
1502:doi
1433:doi
1429:339
1229:doi
929:An
874:In
735:of
651:In
184:of
58:or
42:In
2978::
2942:.
2910:55
2908:,
2882:,
2863:,
2855:,
2841:,
2824:MR
2822:,
2810:29
2787:,
2771:,
2761:,
2740:44
2738:,
2719:,
2713:MR
2711:,
2699:,
2672:28
2670:,
2653:MR
2651:,
2643:,
2631:15
2629:,
2588:,
2578:10
2559:,
2549:,
2537:18
2535:,
2518:MR
2516:,
2506:,
2488:;
2484:;
2468:,
2458:,
2446:23
2444:,
2420:,
2408:;
2390:11
2388:,
2371:XV
2369:,
2348:,
2338:56
2336:,
2319:,
2309:61
2307:,
2288:34
2286:,
2269:,
2259:14
2257:,
2234:,
2224:,
2214:,
2202:48
2200:,
2190:;
2174:,
2162:46
2160:,
2142:MR
2140:,
2130:,
2122:,
2096:,
2086:,
2070:,
2051:,
2020:,
2008:41
2006:,
1974:.
1966:.
1958:.
1948:38
1946:.
1942:.
1919:.
1886:.
1876:.
1868:.
1833:.
1825:.
1815:.
1803:81
1801:.
1797:.
1781:.
1765:.
1742:.
1734:.
1726:.
1714:48
1712:.
1708:.
1685:.
1675:.
1663:.
1640:.
1630:35
1628:.
1624:.
1589:.
1579:.
1571:.
1557:.
1533:,
1508:.
1496:.
1462:;
1441:.
1427:.
1423:.
1245:.
1237:.
1225:25
1223:.
1219:.
1171:A
1155:.
1118:♯P
1101:RP
1097:NP
1089:♯P
981:A
973:.
942:.
915:.
890:.
815:,
672:".
637:.
587:.
572:.
463:A
395:.
156:A
145:A
54:,
50:,
2948:.
2923:.
2916::
2897:.
2890::
2872:.
2859::
2849::
2831:.
2816::
2800:.
2795::
2789:7
2775::
2765::
2753:.
2746::
2728:.
2707::
2701:3
2685:.
2678::
2660:.
2647::
2616:.
2606:5
2603:P
2597:.
2584::
2568:.
2553::
2525:.
2502::
2477:.
2462::
2452::
2431:.
2401:.
2396::
2375:.
2358:.
2344::
2328:.
2315::
2299:.
2294::
2278:.
2265::
2243:.
2228::
2208::
2183:.
2178::
2149:.
2126::
2118::
2082::
2062:.
2047::
2029:.
2014::
1982:.
1954::
1927:.
1894:.
1872::
1862::
1841:.
1819::
1809::
1789:.
1777::
1750:.
1730::
1720::
1693:.
1671::
1648:.
1636::
1610:.
1597:.
1575::
1565::
1537::
1518:.
1504::
1478:.
1466:.
1449:.
1435::
1358:,
1354:,
1350:,
1346:,
1312:.
1300:.
1288:.
1276:.
1253:.
1231::
1168:.
1071::
1027:d
1023:d
1015:d
1011:d
1007:d
1003:d
997:-
995:d
991:d
987:d
880:c
820:5
817:P
799:n
781:c
773:c
758:.
737:G
729:G
705:k
697:k
668:"
623:n
611:n
560:)
557:G
554:(
531:G
511:)
508:G
505:(
475:G
448:)
445:G
442:(
419:)
416:G
413:(
367:e
360:t
353:v
223:)
220:G
217:(
193:G
168:G
122:S
98:S
78:S
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
