1763:
31:
298:
290:
1523:
of this time bound (an estimate for the largest parameter value that could be solved in a reasonable amount of time) is approximately 190. That is, unless additional algorithmic improvements can be found, this algorithm is suitable only for instances whose vertex cover number is 190 or less. Under
1465:, and its idea is to repeatedly choose some vertex and recursively branch, with two cases at each step: place either the current vertex or all its neighbours into the vertex cover. The algorithm for solving vertex cover that achieves the best asymptotic dependence on the parameter runs in time
1429:, an algorithm finds a minimal vertex cover in polynomial time by finding the first leaf in the tree and adding its parent to the minimal vertex cover, then deleting the leaf and parent and all associated edges and continuing repeatedly until no edges remain in the tree.
2087:
Although finding the minimum-size vertex cover is equivalent to finding the maximum-size independent set, as described above, the two problems are not equivalent in an approximation-preserving way: The
Independent Set problem has
2990:
449:
1916:
2308:
covering all hallways (edges) connecting all rooms (nodes) on a floor might model the objective as a vertex cover minimization problem. The problem has also been used to model the elimination of
1093:
736:
1851:
More involved techniques show that there are approximation algorithms with a slightly better approximation factor. For example, an approximation algorithm with an approximation factor of
1715:
1646:
271:
1517:
2052:
1151:
1246:
616:
2078:
1956:
1191:
3164:
3105:
2863:
1022:
1976:
671:
548:
499:
474:
366:
328:
1274:
3371:
1375:
is either 0, 1/2, or 1. A 2-approximate vertex cover can be obtained from this fractional solution by selecting the subset of vertices whose variables are nonzero.
1373:
575:
1575:
1546:
1339:
1315:
959:
939:
916:
896:
860:
840:
820:
798:
523:
386:
264:
1391:, which means it is unlikely that there is an efficient algorithm to solve it exactly for arbitrary graphs. NP-completeness can be proven by reduction from
2712:
Mathematical
Foundations of Computer Science 2006: 31st International Symposium, MFCS 2006, Stará Lesná, Slovakia, August 28-September 1, 2006, Proceedings
2587:
Hossain, Ayaan; Lopez, Eriberto; Halper, Sean M.; Cetnar, Daniel P.; Reis, Alexander C.; Strickland, Devin; Klavins, Eric; Salis, Howard M. (2020-07-13).
3231:
1987:
257:
97:
is true. On the other hand, it has several simple 2-factor approximations. It is a typical example of an NP-hard optimization problem that has an
2642:
Reis, Alexander C.; Halper, Sean M.; Vezeau, Grace E.; Cetnar, Daniel P.; Hossain, Ayaan; Clauer, Phillip R.; Salis, Howard M. (November 2019).
3282:
3200:
3158:
2938:
2857:
2731:
2016:
proved in 2005 that minimum vertex cover cannot be approximated within a factor of 1.3606 for any sufficiently large vertex degree unless
1415:
3125:. DIMACS Series in Discrete Mathematics and Theoretical Computer Science. Vol. 40. American Mathematical Society. pp. 169–178.
759:
Consequently, the number of vertices of a graph is equal to its minimum vertex cover number plus the size of a maximum independent set.
3000:
2771:
2538:
970:
110:
3027:
1321:(allowing each variable to be in the interval from 0 to 1, rather than requiring the variables to be only 0 or 1) gives a factor-
3222:
974:
118:
3143:
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of
Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017
3070:
2842:
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of
Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018
1392:
753:
219:
1854:
391:
3376:
1318:
1294:
1041:
51:
1654:
1525:
157:
676:
3381:
2757:
2528:
2305:
1650:
1450:
122:
1661:
1592:
2555:
638:
145:
126:
1468:
2309:
2081:
1727:
1341:
749:
207:
98:
94:
2027:
3254:
3079:
2893:
1025:
2884:
2317:
1734:
endpoints of an edge into the vertex cover, then removing them from the graph. Put otherwise, we find a
55:
3137:(2017). "On independent sets, 2-to-2 games, and Grassmann graphs". In Hatami, Hamed; McKenzie, Pierre;
1762:
1110:
1206:
2745:
2709:
Chen, Jianer; Kanj, Iyad A.; Xia, Ge (2006). "Improved
Parameterized Upper Bounds for Vertex Cover".
2516:
773:
226:
74:
3084:
2763:
2057:
1344:
for the minimum vertex cover problem. Furthermore, the linear programming relaxation of that ILP is
2898:
2084:
is true then minimum vertex cover cannot be approximated within any constant factor better than 2.
1921:
231:
141:
90:
59:
1158:
3206:
3097:
2836:(2018). "Towards a proof of the 2-to-1 games conjecture?". In Diakonikolas, Ilias; Kempe, David;
2807:
2790:
2687:
2644:"Simultaneous repression of multiple bacterial genes using nonrepetitive extra-long sgRNA arrays"
2624:
2297:
1845:
1438:
167:
1584:, and more generally, for graphs excluding some fixed graph as a minor, a vertex cover of size
992:
580:
2304:
problems. For example, a commercial establishment interested in installing the fewest possible
3339:
3320:
3301:
3278:
3258:
3196:
3154:
3118:
2996:
2934:
2853:
2767:
2727:
2679:
2671:
2663:
2616:
2608:
2566:
2534:
2313:
1290:
243:
190:
178:
2589:"Automated design of thousands of nonrepetitive parts for engineering stable genetic systems"
1961:
643:
333:
3240:
3188:
3146:
3089:
3033:
3019:
3015:
3011:
2986:
2982:
2970:
2958:
2954:
2926:
2903:
2845:
2837:
2799:
2749:
2741:
2719:
2655:
2600:
2512:
1735:
1384:
1253:
867:
631:
238:
183:
102:
66:
1351:
560:
3123:
Proceedings of the DIMACS Workshop on
Network Design: Connectivity and Facilities Location
2301:
1995:
1551:
1458:
1419:
1411:
82:
34:
Example graph that has a vertex cover comprising 2 vertices (bottom), but none with fewer.
2786:"Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs"
2710:
3323:
2718:. Lecture Notes in Computer Science. Vol. 4162. Springer-Verlag. pp. 238–249.
528:
479:
454:
308:
3342:
3270:
2920:
2753:
2524:
2329:
1531:
1396:
1324:
1300:
944:
924:
901:
881:
845:
825:
805:
783:
508:
371:
137:
30:
3365:
2691:
2628:
2643:
297:
17:
3218:
3210:
3176:
3138:
3134:
3130:
3101:
3045:
2916:
2879:
2833:
2829:
2811:
2781:
2588:
2013:
1581:
1404:
618:. The lower figure shows examples of minimum vertex covers in the previous graphs.
133:
39:
3304:
2785:
1024:. The (weighted) minimum vertex cover problem can be formulated as the following
2907:
2005:
1400:
1388:
966:
195:
114:
3245:
3226:
3180:
3168:
3109:
3062:
3023:
2867:
525:. The upper figure shows two examples of vertex covers, with some vertex cover
86:
3356:
2875:
2825:
2784:; Fomin, Fedor V.; Hajiaghayi, Mohammad Taghi; Thilikos, Dimitrios M. (2005).
2659:
2604:
2520:
2009:
1520:
1426:
202:
152:
2667:
2612:
3347:
3328:
3309:
3192:
3150:
3093:
2849:
2803:
2683:
2620:
1817:, then any vertex cover – including an optimal vertex cover – must contain
27:
Subset of a graph's vertices, including at least one endpoint of every edge
3037:
2930:
289:
3185:
2018 IEEE 59th Annual
Symposium on Foundations of Computer Science (FOCS)
1414:, the equivalence between vertex cover and maximum matching described by
2723:
1844:
This simple algorithm was discovered independently by Fanica Gavril and
1918:
is known. The problem can be approximated with an approximation factor
978:
78:
2992:
Computers and
Intractability: A Guide to the Theory of NP-Completeness
2675:
557:
is a vertex cover of smallest possible size. The vertex cover number
3029:
Proceedings of the Sixth Annual ACM Symposium on Theory of
Computing
2974:
3181:"Pseudorandom Sets in Grassmann Graph Have Near-Perfect Expansion"
296:
288:
29:
2882:(2005). "On the hardness of approximating minimum vertex cover".
1990:
than the above one is known. The minimum vertex cover problem is
1348:, that is, there exists an optimal solution for which each entry
93:– it cannot be approximated up to a factor smaller than 2 if the
1653:. This algorithm is again optimal, in the sense that, under the
3227:"Vertex cover might be hard to approximate to within 2−ε"
2961:(1977). "The rectilinear Steiner tree problem is NP-complete".
2533:(2nd ed.). MIT Press and McGraw-Hill. pp. 1024–1027.
1657:, no algorithm can solve vertex cover on planar graphs in time
476:
where every edge has at least one endpoint in the vertex cover
2409:
1994:, that is, it cannot be approximated arbitrarily well unless
1991:
1773:
constructed this way is a vertex cover: suppose that an edge
1829:
is not covered. That is, an optimal cover contains at least
3063:"A better approximation ratio for the vertex cover problem"
1449:
is the size of the vertex cover. Vertex cover is therefore
1418:
allows the bipartite vertex cover problem to be solved in
3145:. Association for Computing Machinery. pp. 576–589.
2844:. Association for Computing Machinery. pp. 376–389.
1841:
is at most 2 times as large as the optimal vertex cover.
2762:. Cambridge, Mass.: MIT Press and McGraw-Hill. pp.
1524:
reasonable complexity-theoretic assumptions, namely the
132:
The minimum vertex cover problem can be formulated as a
1911:{\textstyle 2-\Theta \left(1/{\sqrt {\log |V|}}\right)}
1289:
This ILP belongs to the more general class of ILPs for
748:
A set of vertices is a vertex cover if and only if its
2485:
2432:
2371:
1857:
1528:, the running time cannot be improved to 2, even when
1461:. One algorithmic technique that works here is called
1045:
444:{\displaystyle uv\in E\Rightarrow u\in V'\lor v\in V'}
3263:
2060:
2030:
1964:
1924:
1741:
with a greedy algorithm and construct a vertex cover
1664:
1595:
1554:
1534:
1471:
1354:
1327:
1303:
1256:
1209:
1161:
1113:
1044:
995:
947:
927:
904:
884:
848:
828:
808:
786:
776:
of finding a smallest vertex cover in a given graph.
679:
646:
583:
563:
531:
511:
482:
457:
394:
374:
336:
311:
1797:, which is a contradiction with the assumption that
1281:(every vertex is either in the vertex cover or not)
2527:(2001) . "Section 35.1: The vertex-cover problem".
2459:
989:Assume that every vertex has an associated cost of
3357:River Crossings (and Alcuin Numbers) – Numberphile
2072:
2046:
1970:
1950:
1910:
1709:
1640:
1569:
1540:
1511:
1367:
1333:
1309:
1268:
1240:
1185:
1145:
1088:{\displaystyle \textstyle \sum _{v\in V}c(v)x_{v}}
1087:
1016:
953:
933:
910:
890:
854:
834:
814:
792:
730:
665:
610:
569:
542:
517:
493:
468:
443:
380:
360:
322:
3119:"Approximating dense cases of covering problems"
3117:Karpinski, Marek; Zelikovsky, Alexander (1998).
3048:(1959). "Über extreme Punkt- und Kantenmengen".
708:
2489:
2481:
2435:, p. 432, mentions both Gavril and Yannakakis.
1745:that consists of all endpoints of the edges in
151:Vertex cover problems have been generalized to
1749:. In the following figure, a maximal matching
731:{\displaystyle \tau (K_{m,n})=\min\{\,m,n\,\}}
265:
58:that includes at least one endpoint of every
8:
2436:
2386:
2382:
1235:
1223:
1174:
1162:
725:
711:
577:is the size of a minimum vertex cover, i.e.
3050:Ann. Univ. Sci. Budapest, Eötvös Sect. Math
2398:
1399:. Vertex cover remains NP-complete even in
121:. Furthermore, the vertex cover problem is
2470:
2448:
1710:{\displaystyle 2^{o({\sqrt {k}})}n^{O(1)}}
1641:{\displaystyle 2^{O({\sqrt {k}})}n^{O(1)}}
627:The set of all vertices is a vertex cover.
272:
258:
163:
3244:
3083:
2897:
2500:
2420:
2059:
2031:
2029:
1963:
1928:
1923:
1896:
1888:
1880:
1875:
1856:
1753:is marked with red, and the vertex cover
1692:
1676:
1669:
1663:
1623:
1607:
1600:
1594:
1553:
1533:
1482:
1470:
1453:, and if we are only interested in small
1441:algorithm can solve the problem in time 2
1359:
1353:
1326:
1302:
1255:
1214:
1208:
1160:
1131:
1118:
1112:
1078:
1050:
1043:
994:
946:
926:
903:
883:
847:
827:
807:
785:
724:
714:
690:
678:
651:
645:
603:
590:
582:
562:
530:
510:
481:
456:
451:, that is to say it is a set of vertices
393:
373:
335:
310:
2556:"Approximation Algorithms: Vertex Cover"
2359:
1512:{\displaystyle O(1.2738^{k}+(k\cdot n))}
3232:Journal of Computer and System Sciences
2340:
1988:constant-factor approximation algorithm
1395:or, as Karp did, by reduction from the
1387:variant of the vertex cover problem is
166:
3372:Computational problems in graph theory
3024:"Some simplified NP-complete problems"
2347:
2296:Vertex cover optimization serves as a
1649:, i.e., the problem is subexponential
2092:constant-factor approximation unless
2047:{\displaystyle {\sqrt {2}}-\epsilon }
2024:. Later, the factor was improved to
7:
3061:Karakostas, George (November 2009).
2372:Garey, Johnson & Stockmeyer 1974
941:have a vertex cover of size at most
3179:; Minzer, Dor; Safra, Muli (2018).
2963:SIAM Journal on Applied Mathematics
673:has a minimum vertex cover of size
2433:Papadimitriou & Steiglitz 1998
1864:
25:
2554:Chakrabarti, Amit (Winter 2005).
1197:(cover every edge of the graph),
1146:{\displaystyle x_{u}+x_{v}\geq 1}
301:Examples of minimum vertex covers
1761:
1241:{\displaystyle x_{v}\in \{0,1\}}
2922:Parameterized Complexity Theory
2460:Karpinski & Zelikovsky 1998
975:computational complexity theory
965:The vertex cover problem is an
127:parameterized complexity theory
119:computational complexity theory
3071:ACM Transactions on Algorithms
2073:{\displaystyle \epsilon >0}
1945:
1933:
1897:
1889:
1825:(or both); otherwise the edge
1702:
1696:
1683:
1673:
1633:
1627:
1614:
1604:
1564:
1558:
1506:
1503:
1491:
1475:
1457:, we can solve the problem in
1071:
1065:
1005:
999:
971:Karp's 21 NP-complete problems
866:If the problem is stated as a
702:
683:
604:
591:
407:
355:
343:
168:Covering/packing-problem pairs
111:Karp's 21 NP-complete problems
81:, so it cannot be solved by a
1:
2832:; Kindler, Guy; Minzer, Dor;
2490:Khot, Minzer & Safra 2018
2482:Khot, Minzer & Safra 2017
1951:{\displaystyle 2/(1+\delta )}
1463:bounded search tree algorithm
113:and is therefore a classical
2004:. Using techniques from the
1801:is maximal. Furthermore, if
1433:Fixed-parameter tractability
1186:{\displaystyle \{u,v\}\in E}
842:has a vertex cover of size
770:minimum vertex cover problem
2908:10.4007/annals.2005.162.439
1655:exponential time hypothesis
1526:exponential time hypothesis
158:Vertex cover in hypergraphs
69:, the problem of finding a
3398:
3255:Papadimitriou, Christos H.
3246:10.1016/j.jcss.2007.06.019
2759:Introduction to Algorithms
2530:Introduction to Algorithms
1100:(minimize the total cost)
1017:{\displaystyle c(v)\geq 0}
611:{\displaystyle \tau =|V'|}
2660:10.1038/s41587-019-0286-9
2605:10.1038/s41587-020-0584-2
2399:Chen, Kanj & Xia 2006
1833:endpoint of each edge in
1651:fixed-parameter tractable
1451:fixed-parameter tractable
1038:
305:Formally, a vertex cover
293:Examples of vertex covers
125:and a central problem in
123:fixed-parameter tractable
3275:Approximation Algorithms
2437:Garey & Johnson 1979
2387:Garey & Johnson 1979
2383:Garey & Johnson 1977
2310:repetitive DNA sequences
2300:for many real-world and
2107:
1726:One can find a factor-2
977:as a starting point for
802:OUTPUT: Smallest number
639:complete bipartite graph
501:. Such a set is said to
146:maximum matching problem
3193:10.1109/FOCS.2018.00062
3151:10.1145/3055399.3055432
3094:10.1145/1597036.1597045
2850:10.1145/3188745.3188804
2804:10.1145/1101821.1101823
2439:, p. 134, cites Gavril.
2082:unique games conjecture
1971:{\displaystyle \delta }
1342:approximation algorithm
969:problem: it was one of
666:{\displaystyle K_{m,n}}
361:{\displaystyle G=(V,E)}
330:of an undirected graph
220:Maximum independent set
99:approximation algorithm
95:unique games conjecture
3324:"Minimum Vertex Cover"
2471:Dinur & Safra 2005
2421:Flum & Grohe (2006
2306:closed circuit cameras
2074:
2048:
1972:
1952:
1912:
1722:Approximate evaluation
1711:
1642:
1571:
1542:
1513:
1369:
1335:
1311:
1270:
1269:{\displaystyle v\in V}
1242:
1187:
1147:
1089:
1026:integer linear program
1018:
973:. It is often used in
955:
935:
912:
892:
856:
836:
816:
794:
732:
667:
612:
571:
544:
519:
495:
470:
445:
382:
362:
324:
302:
294:
35:
3343:"Vertex Cover Number"
3038:10.1145/800119.803884
2931:10.1007/3-540-29953-X
2885:Annals of Mathematics
2746:Leiserson, Charles E.
2517:Leiserson, Charles E.
2501:Khot & Regev 2008
2318:metabolic engineering
2075:
2049:
1973:
1953:
1913:
1757:is marked with blue.
1730:by repeatedly taking
1712:
1643:
1588:can be found in time
1572:
1543:
1514:
1407:of degree at most 3.
1370:
1368:{\displaystyle x_{v}}
1336:
1312:
1271:
1243:
1188:
1148:
1090:
1019:
956:
936:
913:
898:and positive integer
893:
857:
837:
817:
795:
764:Computational problem
733:
668:
630:The endpoints of any
613:
572:
570:{\displaystyle \tau }
545:
520:
496:
471:
446:
383:
363:
325:
300:
292:
33:
3377:NP-complete problems
3187:. pp. 592–601.
2648:Nature Biotechnology
2593:Nature Biotechnology
2563:Computer Science 105
2058:
2028:
1962:
1922:
1855:
1837:; in total, the set
1789:} is a matching and
1662:
1593:
1570:{\displaystyle O(k)}
1552:
1532:
1469:
1352:
1325:
1301:
1254:
1207:
1159:
1111:
1042:
993:
945:
925:
902:
882:
872:vertex cover problem
846:
826:
806:
784:
774:optimization problem
677:
644:
634:form a vertex cover.
581:
561:
555:minimum vertex cover
529:
509:
480:
455:
392:
372:
334:
309:
215:Minimum vertex cover
107:vertex cover problem
75:optimization problem
71:minimum vertex cover
18:Vertex cover problem
3277:. Springer-Verlag.
2724:10.1007/11821069_21
2410:Demaine et al. 2005
2080:. Moreover, if the
870:, it is called the
196:Maximum set packing
142:dual linear program
91:hard to approximate
3340:Weisstein, Eric W.
3321:Weisstein, Eric W.
3302:Weisstein, Eric W.
3271:Vazirani, Vijay V.
3259:Steiglitz, Kenneth
3032:. pp. 47–63.
3007:A1.1: GT1, pg.190.
2791:Journal of the ACM
2389:, pp. 190 and 195.
2362:, pp. 121–122
2070:
2044:
1968:
1948:
1908:
1846:Mihalis Yannakakis
1777:is not covered by
1707:
1638:
1567:
1538:
1509:
1365:
1331:
1307:
1266:
1238:
1183:
1143:
1085:
1084:
1061:
1014:
951:
931:
908:
888:
852:
832:
812:
790:
728:
663:
608:
567:
543:{\displaystyle V'}
540:
515:
494:{\displaystyle V'}
491:
469:{\displaystyle V'}
466:
441:
378:
358:
323:{\displaystyle V'}
320:
303:
295:
203:Minimum edge cover
89:. Moreover, it is
36:
3382:Covering problems
3284:978-3-662-04565-7
3202:978-1-5386-4230-6
3160:978-1-4503-4528-6
3020:Stockmeyer, Larry
3016:Johnson, David S.
3012:Garey, Michael R.
2987:Johnson, David S.
2983:Garey, Michael R.
2959:Johnson, David S.
2955:Garey, Michael R.
2940:978-3-540-29952-3
2859:978-1-4503-5559-9
2838:Henzinger, Monika
2750:Rivest, Ronald L.
2742:Cormen, Thomas H.
2733:978-3-540-37791-7
2654:(11): 1294–1301.
2599:(12): 1466–1475.
2567:Dartmouth College
2521:Rivest, Ronald L.
2513:Cormen, Thomas H.
2486:Dinur et al. 2018
2314:synthetic biology
2036:
1982:Inapproximability
1901:
1681:
1612:
1541:{\displaystyle n}
1439:exhaustive search
1334:{\displaystyle 2}
1310:{\displaystyle 2}
1291:covering problems
1285:
1284:
1046:
954:{\displaystyle k}
934:{\displaystyle G}
911:{\displaystyle k}
891:{\displaystyle G}
855:{\displaystyle k}
835:{\displaystyle G}
815:{\displaystyle k}
793:{\displaystyle G}
518:{\displaystyle G}
381:{\displaystyle V}
282:
281:
249:
248:
244:Rectangle packing
191:Minimum set cover
179:Covering problems
16:(Redirected from
3389:
3353:
3352:
3334:
3333:
3315:
3314:
3288:
3266:
3250:
3248:
3214:
3172:
3126:
3113:
3087:
3078:(4): 41:1–41:8.
3067:
3057:
3041:
3006:
2995:. W.H. Freeman.
2978:
2950:
2948:
2947:
2911:
2901:
2871:
2821:
2819:
2818:
2777:
2737:
2717:
2696:
2695:
2639:
2633:
2632:
2584:
2578:
2577:
2575:
2573:
2560:
2551:
2545:
2544:
2509:
2503:
2498:
2492:
2479:
2473:
2468:
2462:
2457:
2451:
2446:
2440:
2430:
2424:
2418:
2412:
2407:
2401:
2396:
2390:
2380:
2374:
2369:
2363:
2357:
2351:
2345:
2285:
2282:
2279:
2276:
2273:
2270:
2267:
2264:
2261:
2258:
2255:
2252:
2249:
2246:
2243:
2240:
2237:
2234:
2231:
2228:
2225:
2222:
2219:
2216:
2213:
2210:
2207:
2204:
2201:
2198:
2195:
2192:
2189:
2186:
2183:
2180:
2177:
2174:
2171:
2168:
2165:
2162:
2159:
2156:
2153:
2150:
2147:
2144:
2141:
2138:
2135:
2132:
2129:
2126:
2123:
2120:
2117:
2114:
2111:
2079:
2077:
2076:
2071:
2053:
2051:
2050:
2045:
2037:
2032:
1978:- dense graphs.
1977:
1975:
1974:
1969:
1957:
1955:
1954:
1949:
1932:
1917:
1915:
1914:
1909:
1907:
1903:
1902:
1900:
1892:
1881:
1879:
1765:
1736:maximal matching
1716:
1714:
1713:
1708:
1706:
1705:
1687:
1686:
1682:
1677:
1647:
1645:
1644:
1639:
1637:
1636:
1618:
1617:
1613:
1608:
1576:
1574:
1573:
1568:
1547:
1545:
1544:
1539:
1518:
1516:
1515:
1510:
1487:
1486:
1412:bipartite graphs
1393:3-satisfiability
1379:Exact evaluation
1374:
1372:
1371:
1366:
1364:
1363:
1340:
1338:
1337:
1332:
1316:
1314:
1313:
1308:
1275:
1273:
1272:
1267:
1247:
1245:
1244:
1239:
1219:
1218:
1192:
1190:
1189:
1184:
1152:
1150:
1149:
1144:
1136:
1135:
1123:
1122:
1094:
1092:
1091:
1086:
1083:
1082:
1060:
1033:
1032:
1023:
1021:
1020:
1015:
960:
958:
957:
952:
940:
938:
937:
932:
917:
915:
914:
909:
897:
895:
894:
889:
878:INSTANCE: Graph
868:decision problem
861:
859:
858:
853:
841:
839:
838:
833:
821:
819:
818:
813:
799:
797:
796:
791:
780:INSTANCE: Graph
737:
735:
734:
729:
701:
700:
672:
670:
669:
664:
662:
661:
632:maximal matching
617:
615:
614:
609:
607:
602:
594:
576:
574:
573:
568:
549:
547:
546:
541:
539:
524:
522:
521:
516:
500:
498:
497:
492:
490:
475:
473:
472:
467:
465:
450:
448:
447:
442:
440:
423:
387:
385:
384:
379:
367:
365:
364:
359:
329:
327:
326:
321:
319:
274:
267:
260:
239:Polygon covering
208:Maximum matching
184:Packing problems
175:
174:
164:
103:decision version
67:computer science
21:
3397:
3396:
3392:
3391:
3390:
3388:
3387:
3386:
3362:
3361:
3338:
3337:
3319:
3318:
3300:
3299:
3296:
3291:
3285:
3269:
3253:
3217:
3203:
3175:
3161:
3133:; Minzer, Dor;
3129:
3116:
3085:10.1.1.649.7407
3065:
3060:
3044:
3010:
3003:
2981:
2975:10.1137/0132071
2953:
2945:
2943:
2941:
2914:
2874:
2860:
2824:
2816:
2814:
2780:
2774:
2754:Stein, Clifford
2740:
2734:
2715:
2708:
2704:
2699:
2641:
2640:
2636:
2586:
2585:
2581:
2571:
2569:
2558:
2553:
2552:
2548:
2541:
2525:Stein, Clifford
2511:
2510:
2506:
2499:
2495:
2480:
2476:
2469:
2465:
2458:
2454:
2449:Karakostas 2009
2447:
2443:
2431:
2427:
2419:
2415:
2408:
2404:
2397:
2393:
2381:
2377:
2370:
2366:
2358:
2354:
2346:
2342:
2338:
2326:
2294:
2287:
2286:
2283:
2280:
2277:
2274:
2271:
2268:
2265:
2262:
2259:
2256:
2253:
2250:
2247:
2244:
2241:
2238:
2235:
2232:
2229:
2226:
2223:
2220:
2217:
2214:
2211:
2208:
2205:
2202:
2199:
2196:
2193:
2190:
2187:
2184:
2181:
2178:
2175:
2172:
2169:
2166:
2163:
2160:
2157:
2154:
2151:
2148:
2145:
2142:
2139:
2136:
2133:
2130:
2127:
2124:
2121:
2118:
2115:
2112:
2109:
2106:
2056:
2055:
2026:
2025:
1984:
1960:
1959:
1920:
1919:
1871:
1867:
1853:
1852:
1724:
1688:
1665:
1660:
1659:
1619:
1596:
1591:
1590:
1550:
1549:
1530:
1529:
1478:
1467:
1466:
1459:polynomial time
1435:
1420:polynomial time
1416:Kőnig's theorem
1381:
1355:
1350:
1349:
1323:
1322:
1299:
1298:
1297:of this ILP is
1295:integrality gap
1252:
1251:
1210:
1205:
1204:
1157:
1156:
1127:
1114:
1109:
1108:
1074:
1040:
1039:
991:
990:
987:
985:ILP formulation
943:
942:
923:
922:
921:QUESTION: Does
900:
899:
880:
879:
844:
843:
824:
823:
804:
803:
782:
781:
766:
754:independent set
745:
686:
675:
674:
647:
642:
641:
624:
595:
579:
578:
559:
558:
550:marked in red.
532:
527:
526:
507:
506:
483:
478:
477:
458:
453:
452:
433:
416:
390:
389:
370:
369:
368:is a subset of
332:
331:
312:
307:
306:
287:
278:
83:polynomial-time
73:is a classical
62:of the graph.
28:
23:
22:
15:
12:
11:
5:
3395:
3393:
3385:
3384:
3379:
3374:
3364:
3363:
3360:
3359:
3354:
3335:
3316:
3305:"Vertex Cover"
3295:
3294:External links
3292:
3290:
3289:
3283:
3267:
3251:
3239:(3): 335–349.
3215:
3201:
3173:
3159:
3127:
3114:
3058:
3042:
3008:
3001:
2979:
2969:(4): 826–834.
2951:
2939:
2912:
2899:10.1.1.125.334
2892:(1): 439–485.
2872:
2858:
2822:
2798:(6): 866–893.
2778:
2772:
2738:
2732:
2705:
2703:
2700:
2698:
2697:
2634:
2579:
2546:
2539:
2504:
2493:
2474:
2463:
2452:
2441:
2425:
2423:, p. 437)
2413:
2402:
2391:
2375:
2364:
2352:
2339:
2337:
2334:
2333:
2332:
2330:Dominating set
2325:
2322:
2320:applications.
2293:
2290:
2108:
2105:
2102:
2069:
2066:
2063:
2043:
2040:
2035:
1983:
1980:
1967:
1947:
1944:
1941:
1938:
1935:
1931:
1927:
1906:
1899:
1895:
1891:
1887:
1884:
1878:
1874:
1870:
1866:
1863:
1860:
1805: = {
1785: ∪ {
1767:
1766:
1723:
1720:
1704:
1701:
1698:
1695:
1691:
1685:
1680:
1675:
1672:
1668:
1635:
1632:
1629:
1626:
1622:
1616:
1611:
1606:
1603:
1599:
1566:
1563:
1560:
1557:
1537:
1508:
1505:
1502:
1499:
1496:
1493:
1490:
1485:
1481:
1477:
1474:
1434:
1431:
1397:clique problem
1380:
1377:
1362:
1358:
1330:
1306:
1287:
1286:
1283:
1282:
1279:
1277:
1265:
1262:
1259:
1248:
1237:
1234:
1231:
1228:
1225:
1222:
1217:
1213:
1202:
1199:
1198:
1195:
1193:
1182:
1179:
1176:
1173:
1170:
1167:
1164:
1153:
1142:
1139:
1134:
1130:
1126:
1121:
1117:
1106:
1102:
1101:
1098:
1095:
1081:
1077:
1073:
1070:
1067:
1064:
1059:
1056:
1053:
1049:
1037:
1013:
1010:
1007:
1004:
1001:
998:
986:
983:
963:
962:
950:
930:
919:
907:
887:
864:
863:
851:
831:
811:
800:
789:
765:
762:
761:
760:
757:
744:
741:
740:
739:
727:
723:
720:
717:
713:
710:
707:
704:
699:
696:
693:
689:
685:
682:
660:
657:
654:
650:
635:
628:
623:
620:
606:
601:
598:
593:
589:
586:
566:
538:
535:
514:
489:
486:
464:
461:
439:
436:
432:
429:
426:
422:
419:
415:
412:
409:
406:
403:
400:
397:
377:
357:
354:
351:
348:
345:
342:
339:
318:
315:
286:
283:
280:
279:
277:
276:
269:
262:
254:
251:
250:
247:
246:
241:
235:
234:
229:
223:
222:
217:
211:
210:
205:
199:
198:
193:
187:
186:
181:
171:
170:
138:linear program
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
3394:
3383:
3380:
3378:
3375:
3373:
3370:
3369:
3367:
3358:
3355:
3350:
3349:
3344:
3341:
3336:
3331:
3330:
3325:
3322:
3317:
3312:
3311:
3306:
3303:
3298:
3297:
3293:
3286:
3280:
3276:
3272:
3268:
3264:
3260:
3256:
3252:
3247:
3242:
3238:
3234:
3233:
3228:
3224:
3220:
3219:Khot, Subhash
3216:
3212:
3208:
3204:
3198:
3194:
3190:
3186:
3182:
3178:
3177:Khot, Subhash
3174:
3170:
3166:
3162:
3156:
3152:
3148:
3144:
3140:
3139:King, Valerie
3136:
3132:
3131:Khot, Subhash
3128:
3124:
3120:
3115:
3111:
3107:
3103:
3099:
3095:
3091:
3086:
3081:
3077:
3073:
3072:
3064:
3059:
3055:
3051:
3047:
3046:Gallai, Tibor
3043:
3039:
3035:
3031:
3030:
3025:
3021:
3017:
3013:
3009:
3004:
3002:0-7167-1045-5
2998:
2994:
2993:
2988:
2984:
2980:
2976:
2972:
2968:
2964:
2960:
2956:
2952:
2942:
2936:
2932:
2928:
2924:
2923:
2918:
2917:Grohe, Martin
2913:
2909:
2905:
2900:
2895:
2891:
2887:
2886:
2881:
2880:Safra, Samuel
2877:
2873:
2869:
2865:
2861:
2855:
2851:
2847:
2843:
2839:
2835:
2831:
2830:Khot, Subhash
2827:
2823:
2813:
2809:
2805:
2801:
2797:
2793:
2792:
2787:
2783:
2782:Demaine, Erik
2779:
2775:
2773:0-262-03293-7
2769:
2765:
2761:
2760:
2755:
2751:
2747:
2743:
2739:
2735:
2729:
2725:
2721:
2714:
2713:
2707:
2706:
2701:
2693:
2689:
2685:
2681:
2677:
2673:
2669:
2665:
2661:
2657:
2653:
2649:
2645:
2638:
2635:
2630:
2626:
2622:
2618:
2614:
2610:
2606:
2602:
2598:
2594:
2590:
2583:
2580:
2568:
2564:
2557:
2550:
2547:
2542:
2540:0-262-03293-7
2536:
2532:
2531:
2526:
2522:
2518:
2514:
2508:
2505:
2502:
2497:
2494:
2491:
2487:
2483:
2478:
2475:
2472:
2467:
2464:
2461:
2456:
2453:
2450:
2445:
2442:
2438:
2434:
2429:
2426:
2422:
2417:
2414:
2411:
2406:
2403:
2400:
2395:
2392:
2388:
2384:
2379:
2376:
2373:
2368:
2365:
2361:
2360:Vazirani 2003
2356:
2353:
2349:
2344:
2341:
2335:
2331:
2328:
2327:
2323:
2321:
2319:
2315:
2311:
2307:
2303:
2299:
2291:
2289:
2110:APPROXIMATION
2103:
2101:
2099:
2096: =
2095:
2091:
2085:
2083:
2067:
2064:
2061:
2041:
2038:
2033:
2023:
2020: =
2019:
2015:
2011:
2007:
2003:
2002:
1999: =
1998:
1993:
1989:
1981:
1979:
1965:
1942:
1939:
1936:
1929:
1925:
1904:
1893:
1885:
1882:
1876:
1872:
1868:
1861:
1858:
1849:
1847:
1842:
1840:
1836:
1832:
1828:
1824:
1820:
1816:
1812:
1808:
1804:
1800:
1796:
1793: ∉
1792:
1788:
1784:
1780:
1776:
1772:
1764:
1760:
1759:
1758:
1756:
1752:
1748:
1744:
1740:
1737:
1733:
1729:
1728:approximation
1721:
1719:
1717:
1699:
1693:
1689:
1678:
1670:
1666:
1656:
1652:
1648:
1630:
1624:
1620:
1609:
1601:
1597:
1587:
1583:
1582:planar graphs
1580:However, for
1578:
1561:
1555:
1535:
1527:
1522:
1500:
1497:
1494:
1488:
1483:
1479:
1472:
1464:
1460:
1456:
1452:
1448:
1444:
1440:
1432:
1430:
1428:
1423:
1421:
1417:
1413:
1408:
1406:
1405:planar graphs
1402:
1398:
1394:
1390:
1386:
1378:
1376:
1360:
1356:
1347:
1346:half-integral
1343:
1328:
1320:
1304:
1296:
1292:
1280:
1278:
1263:
1260:
1257:
1249:
1232:
1229:
1226:
1220:
1215:
1211:
1203:
1201:
1200:
1196:
1194:
1180:
1177:
1171:
1168:
1165:
1154:
1140:
1137:
1132:
1128:
1124:
1119:
1115:
1107:
1104:
1103:
1099:
1097:
1096:
1079:
1075:
1068:
1062:
1057:
1054:
1051:
1047:
1035:
1034:
1031:
1030:
1029:
1027:
1011:
1008:
1002:
996:
984:
982:
980:
976:
972:
968:
948:
928:
920:
905:
885:
877:
876:
875:
873:
869:
849:
829:
809:
801:
787:
779:
778:
777:
775:
771:
763:
758:
755:
751:
747:
746:
742:
721:
718:
715:
705:
697:
694:
691:
687:
680:
658:
655:
652:
648:
640:
636:
633:
629:
626:
625:
621:
619:
599:
596:
587:
584:
564:
556:
551:
536:
533:
512:
505:the edges of
504:
487:
484:
462:
459:
437:
434:
430:
427:
424:
420:
417:
413:
410:
404:
401:
398:
395:
375:
352:
349:
346:
340:
337:
316:
313:
299:
291:
284:
275:
270:
268:
263:
261:
256:
255:
253:
252:
245:
242:
240:
237:
236:
233:
230:
228:
225:
224:
221:
218:
216:
213:
212:
209:
206:
204:
201:
200:
197:
194:
192:
189:
188:
185:
182:
180:
177:
176:
173:
172:
169:
165:
162:
160:
159:
154:
149:
147:
143:
139:
135:
134:half-integral
130:
128:
124:
120:
116:
112:
109:, was one of
108:
104:
100:
96:
92:
88:
85:algorithm if
84:
80:
76:
72:
68:
63:
61:
57:
53:
49:
45:
41:
32:
19:
3346:
3327:
3308:
3274:
3262:
3236:
3230:
3184:
3142:
3122:
3075:
3069:
3053:
3049:
3028:
2991:
2966:
2962:
2944:. Retrieved
2925:. Springer.
2921:
2915:Flum, Jörg;
2889:
2883:
2841:
2815:. Retrieved
2795:
2789:
2758:
2711:
2651:
2647:
2637:
2596:
2592:
2582:
2570:. Retrieved
2562:
2549:
2529:
2507:
2496:
2477:
2466:
2455:
2444:
2428:
2416:
2405:
2394:
2378:
2367:
2355:
2343:
2295:
2292:Applications
2288:
2097:
2093:
2089:
2086:
2021:
2017:
2000:
1996:
1992:APX-complete
1985:
1850:
1843:
1838:
1834:
1830:
1826:
1822:
1818:
1814:
1810:
1806:
1802:
1798:
1794:
1790:
1786:
1782:
1778:
1774:
1770:
1768:
1754:
1750:
1746:
1742:
1738:
1731:
1725:
1658:
1589:
1585:
1579:
1462:
1454:
1446:
1442:
1436:
1424:
1409:
1403:and even in
1401:cubic graphs
1382:
1345:
1288:
988:
964:
871:
865:
769:
767:
554:
552:
502:
304:
227:Bin covering
214:
156:
150:
131:
106:
70:
64:
54:is a set of
47:
44:vertex cover
43:
40:graph theory
37:
3223:Regev, Oded
3135:Safra, Muli
2876:Dinur, Irit
2834:Safra, Muli
2826:Dinur, Irit
2572:21 February
2348:Gallai 1959
2302:theoretical
2006:PCP theorem
1427:tree graphs
1389:NP-complete
1105:subject to
979:NP-hardness
967:NP-complete
232:Bin packing
153:hypergraphs
117:problem in
115:NP-complete
46:(sometimes
3366:Categories
3056:: 133–138.
2946:2010-03-05
2817:2010-03-05
2702:References
2104:Pseudocode
1986:No better
1521:klam value
1319:relaxation
822:such that
750:complement
743:Properties
388:such that
285:Definition
48:node cover
3348:MathWorld
3329:MathWorld
3310:MathWorld
3080:CiteSeerX
2894:CiteSeerX
2692:203852115
2668:1546-1696
2629:220506228
2613:1087-0156
2203:arbitrary
2062:ϵ
2042:ϵ
2039:−
1966:δ
1943:δ
1886:
1865:Θ
1862:−
1498:⋅
1317:, so its
1261:∈
1221:∈
1178:∈
1138:≥
1055:∈
1048:∑
1036:minimize
1009:≥
681:τ
585:τ
565:τ
431:∈
425:∨
414:∈
408:⇒
402:∈
3273:(2003).
3265:. Dover.
3261:(1998).
3225:(2008).
3169:TR16-124
3141:(eds.).
3110:TR04-084
3022:(1974).
2989:(1979).
2919:(2006).
2868:TR16-198
2840:(eds.).
2756:(2001).
2684:31591552
2621:32661437
2324:See also
2263:incident
2054:for any
1769:The set
1445:, where
1385:decision
1250:for all
1155:for all
981:proofs.
622:Examples
600:′
537:′
488:′
463:′
438:′
421:′
317:′
77:. It is
56:vertices
3211:3688775
3102:2525818
2812:6238832
2766:–1027.
2676:1569832
1809:,
1781:; then
1028:(ILP).
772:is the
144:is the
79:NP-hard
50:) of a
3281:
3209:
3199:
3167:
3157:
3108:
3100:
3082:
2999:
2937:
2896:
2866:
2856:
2810:
2770:
2730:
2690:
2682:
2674:
2666:
2627:
2619:
2611:
2537:
2281:return
2269:either
2245:remove
2116:VERTEX
1519:. The
1480:1.2738
1293:. The
752:is an
155:, see
140:whose
105:, the
101:. Its
87:P ≠ NP
3207:S2CID
3098:S2CID
3066:(PDF)
2808:S2CID
2716:(PDF)
2688:S2CID
2625:S2CID
2559:(PDF)
2336:Notes
2298:model
2257:every
2254:'
2215:'
2167:'
2161:while
2146:'
2122:COVER
2014:Safra
2010:Dinur
503:cover
52:graph
3279:ISBN
3197:ISBN
3165:ECCC
3155:ISBN
3106:ECCC
2997:ISBN
2935:ISBN
2864:ECCC
2854:ISBN
2768:ISBN
2764:1024
2728:ISBN
2680:PMID
2672:OSTI
2664:ISSN
2617:PMID
2609:ISSN
2574:2005
2535:ISBN
2316:and
2312:for
2260:edge
2248:from
2206:edge
2065:>
2012:and
1813:} ∈
1732:both
1425:For
1410:For
1383:The
768:The
637:The
60:edge
42:, a
3241:doi
3189:doi
3147:doi
3090:doi
3034:doi
2971:doi
2927:doi
2904:doi
2890:162
2846:doi
2800:doi
2720:doi
2656:doi
2601:doi
2179:let
1958:in
1883:log
1831:one
1821:or
1548:is
1437:An
709:min
65:In
38:In
3368::
3345:.
3326:.
3307:.
3257:;
3237:74
3235:.
3229:.
3221:;
3205:.
3195:.
3183:.
3163:.
3153:.
3121:.
3104:.
3096:.
3088:.
3074:.
3068:.
3052:.
3026:.
3018:;
3014:;
2985:;
2967:32
2965:.
2957:;
2933:.
2902:.
2888:.
2878:;
2862:.
2852:.
2828:;
2806:.
2796:52
2794:.
2788:.
2752:;
2748:;
2744:;
2726:.
2686:.
2678:.
2670:.
2662:.
2652:37
2650:.
2646:.
2623:.
2615:.
2607:.
2597:38
2595:.
2591:.
2565:.
2561:.
2523:;
2519:;
2515:;
2488:;
2484:;
2385:;
2275:or
2266:on
2209:of
2200:an
2197:be
2100:.
2098:NP
2090:no
2022:NP
2008:,
2001:NP
1848:.
1718:.
1577:.
1422:.
1276:.
874::
553:A
161:.
148:.
136:,
129:.
3351:.
3332:.
3313:.
3287:.
3249:.
3243::
3213:.
3191::
3171:.
3149::
3112:.
3092::
3076:5
3054:2
3040:.
3036::
3005:.
2977:.
2973::
2949:.
2929::
2910:.
2906::
2870:.
2848::
2820:.
2802::
2776:.
2736:.
2722::
2694:.
2658::
2631:.
2603::
2576:.
2543:.
2350:.
2284:C
2278:v
2272:u
2251:E
2242:}
2239:v
2236:,
2233:u
2230:{
2227:∪
2224:C
2221:=
2218:C
2212:E
2194:)
2191:v
2188:,
2185:u
2182:(
2176::
2173:∅
2170:≠
2164:E
2158:E
2155:.
2152:G
2149:=
2143:E
2140:∅
2137:=
2134:C
2131:)
2128:G
2125:(
2119:-
2113:-
2094:P
2068:0
2034:2
2018:P
1997:P
1946:)
1940:+
1937:1
1934:(
1930:/
1926:2
1905:)
1898:|
1894:V
1890:|
1877:/
1873:1
1869:(
1859:2
1839:C
1835:M
1827:e
1823:v
1819:u
1815:M
1811:v
1807:u
1803:e
1799:M
1795:M
1791:e
1787:e
1783:M
1779:C
1775:e
1771:C
1755:C
1751:M
1747:M
1743:C
1739:M
1703:)
1700:1
1697:(
1694:O
1690:n
1684:)
1679:k
1674:(
1671:o
1667:2
1634:)
1631:1
1628:(
1625:O
1621:n
1615:)
1610:k
1605:(
1602:O
1598:2
1586:k
1565:)
1562:k
1559:(
1556:O
1536:n
1507:)
1504:)
1501:n
1495:k
1492:(
1489:+
1484:k
1476:(
1473:O
1455:k
1447:k
1443:n
1361:v
1357:x
1329:2
1305:2
1264:V
1258:v
1236:}
1233:1
1230:,
1227:0
1224:{
1216:v
1212:x
1181:E
1175:}
1172:v
1169:,
1166:u
1163:{
1141:1
1133:v
1129:x
1125:+
1120:u
1116:x
1080:v
1076:x
1072:)
1069:v
1066:(
1063:c
1058:V
1052:v
1012:0
1006:)
1003:v
1000:(
997:c
961:?
949:k
929:G
918:.
906:k
886:G
862:.
850:k
830:G
810:k
788:G
756:.
738:.
726:}
722:n
719:,
716:m
712:{
706:=
703:)
698:n
695:,
692:m
688:K
684:(
659:n
656:,
653:m
649:K
605:|
597:V
592:|
588:=
534:V
513:G
485:V
460:V
435:V
428:v
418:V
411:u
405:E
399:v
396:u
376:V
356:)
353:E
350:,
347:V
344:(
341:=
338:G
314:V
273:e
266:t
259:v
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
