35:
that achieve their efficiency by a preprocessing stage in which inputs to the algorithm are replaced by a smaller input, called a "kernel". The result of solving the problem on the kernel should either be the same as on the original input, or it should be easy to transform the output on the kernel to
3666:
above is chosen as the size of the desired solution, this is not necessary. It is also possible to choose a structural complexity measure of the input as the parameter value, leading to so-called structural parameterizations. This approach is fruitful for instances whose solution size is large, but
742:
Although this bound is fixed-parameter tractable, its dependence on the parameter is higher than might be desired. More complex kernelization procedures can improve this bound, by finding smaller kernels, at the expense of greater running time in the kernelization step. In the vertex cover example,
51:
algorithm whose running time is the sum of the (polynomial time) kernelization step and the (non-polynomial but bounded by the parameter) time to solve the kernel. Indeed, every problem that can be solved by a fixed-parameter tractable algorithm can be solved by a kernelization algorithm of this
2414:
The other direction, that a fixed-parameter tractable problem is kernelizable and decidable is a bit more involved. Assume that the question is non-trivial, meaning that there is at least one instance that is in the language, called
285:
since otherwise too many of its neighbors would have to be picked to cover the incident edges. Thus, an optimal vertex cover for the original graph may be formed from a cover of the reduced problem by adding
1100:
878:, unless P = NP, for such a kernel would lead to a polynomial-time algorithm for the NP-hard vertex cover problem. However, much stronger bounds on the kernel size can be proven in this case: unless
3617:
3478:
3330:
3198:
1652:
2996:
2903:
2478:; otherwise, replacing any instance by the empty string is a valid kernelization. Assume also that the problem is fixed-parameter tractable, i.e., it has an algorithm that runs in at most
1611:
3448:
3300:
3168:
2284:
974:
3126:
2528:
1533:
1352:
1255:
637:
1035:
1009:
932:
2185:
2067:
1705:
899:
818:
43:, it is often possible to prove that a kernel with guaranteed bounds on the size of a kernel (as a function of some parameter associated to the problem) can be found in
2758:
2652:
876:
3814:
3406:
3254:
3100:
2124:
3839:
3778:
2685:
2446:
2351:
1562:
1467:
1400:
3370:
2715:
2476:
571:
163:
4165:
2822:
2790:
2560:
2141:
That a kernelizable and decidable problem is fixed-parameter tractable can be seen from the definition above: First the kernelization algorithm, which runs in time
1290:
1163:
541:
484:
377:
3025:
2609:
2409:
2380:
2313:
2214:
1193:
510:
3989:
3966:
3064:
764:
3879:
3859:
3753:
3733:
3715:
problem parameterized by the feedback vertex number of the input graph has a polynomial kernelization: There is a polynomial-time algorithm that, given a graph
3709:
3689:
3660:
3587:
3567:
3547:
3523:
3501:
3218:
2580:
2087:
2025:
2002:
1982:
1962:
1938:
1918:
1898:
1875:
1855:
1835:
1815:
1792:
1772:
1752:
1732:
1676:
1487:
1440:
1420:
1372:
1310:
1213:
1131:
1045:
In the literature, there is no clear consensus on how kernelization should be formally defined and there are subtle differences in the uses of that expression.
838:
737:
717:
697:
677:
657:
457:
437:
417:
397:
347:
327:
304:
283:
263:
243:
223:
203:
183:
129:
109:
89:
1564:
just refers to its length. Some authors prefer to use the number of vertices or the number of edges as the size measure in the context of graph problems.
131:
vertices that includes an endpoint of every edge in the graph, if such a set exists, or a failure exception if no such set exists. This problem is
4113:
4579:
Cygan, Marek; Fomin, Fedor V.; Kowalik, Lukasz; Lokshtanov, Daniel; Marx, Daniel; Pilipczuk, Marcin; Pilipczuk, Michal; Saurabh, Saket (2015),
4588:
4343:
4260:
3896:
53:
516:
An algorithm that applies these rules repeatedly until no more reductions can be made necessarily terminates with a kernel that has at most
4369:
Jansen, Bart M. P.; Bodlaender, Hans L. (2013), "Vertex Cover
Kernelization Revisited - Upper and Lower Bounds for a Refined Parameter",
4137:
4536:
581:
algorithm that tests whether each subset of the kernel is a cover of the kernel. Thus, the vertex cover problem can be solved in time
379:
edges remain in the graph, and neither of the previous two rules can be applied, then the graph cannot contain a vertex cover of size
39:
Kernelization is often achieved by applying a set of reduction rules that cut away parts of the instance that are easy to handle. In
4606:
4559:
4491:
4302:
2216:. The kernel is then solved by the algorithm that proves that the problem is decidable. The total running time of this procedure is
774:
and
Trotter. Another kernelization algorithm achieving that bound is based on what is known as the crown reduction rule and uses
4611:
4549:
4471:
1064:
905:
4416:
3592:
3453:
3305:
3173:
4333:
4239:
1616:
3861:
in polynomial time. The kernelization algorithm therefore guarantees that instances with a small feedback vertex number
48:
2908:
4359:
Fomin, Fedor V.; Lokshtanov, Daniel; Saurabh, Saket; Thilikos, Dimitrios M. (2010), "Bidimensionality and kernels",
2827:
4169:
40:
4199:
3629:
problems have linear kernels on planar graphs, and more generally, on graphs excluding some fixed graph as a
1583:
775:
3411:
3263:
3131:
4477:
778:
arguments. The currently best known kernelization algorithm in terms of the number of vertices is due to
3890:
2219:
937:
3105:
2481:
584:
3900:
3630:
1014:
979:
911:
4233:"Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses"
3526:
3339:
543:
edges and (because each edge has at most two endpoints and there are no isolated vertices) at most
4482:
4232:
486:
edges. In this case, the instance may be replaced by an instance with two vertices, one edge, and
4458:
4378:
4316:
4266:
4219:
4186:
4100:
2135:
578:
2144:
2030:
1681:
884:
785:
2720:
2614:
846:
766:
vertices. One algorithm that achieves this improved bound exploits the half-integrality of the
4584:
4555:
4532:
4487:
4339:
4298:
4256:
3783:
3375:
3223:
3069:
2092:
4086:
2657:
2418:
2318:
1496:
1315:
1218:
329:
is an isolated vertex, remove it. An isolated vertex cannot cover any edges, so in this case
4545:
4524:
4450:
4425:
4388:
4290:
4248:
4211:
4178:
4122:
4082:
3626:
3345:
2690:
2451:
1103:
771:
546:
142:
69:
24:
4312:
4143:
2795:
2763:
2533:
1263:
1136:
519:
462:
355:
4308:
4282:
4108:
4078:
3257:
3001:
2998:. This size bound is computable, by the assumption from fixed-parameter tractability that
2585:
2385:
2356:
2289:
2190:
44:
1168:
489:
3971:
3948:
3819:
3758:
3046:
1542:
1447:
1380:
746:
3864:
3844:
3738:
3718:
3694:
3674:
3645:
3572:
3552:
3532:
3508:
3486:
3203:
2565:
2072:
2010:
1987:
1967:
1947:
1923:
1903:
1883:
1860:
1840:
1820:
1800:
1777:
1757:
1737:
1717:
1661:
1472:
1425:
1405:
1357:
1295:
1198:
1116:
823:
722:
702:
682:
662:
642:
442:
422:
402:
382:
332:
312:
289:
268:
248:
228:
208:
188:
168:
114:
94:
74:
16:
This article is about complexity theory. For kernelized machine learning methods, see
4600:
17:
4565:
4497:
4320:
4223:
4190:
577:. Once the kernel has been constructed, the vertex cover problem may be solved by a
4462:
4329:
4270:
3712:
3040:
767:
65:
574:
4127:
3691:
is defined as the minimum cardinality of a set of vertices whose removal makes
4429:
4393:
4294:
4278:
4104:
4361:
Proceedings of the 21st ACM-SIAM Symposium on
Discrete Algorithms (SODA 2010)
4088:
Kernelization
Algorithms for the Vertex Cover Problem: Theory and Experiments
2134:
A problem is fixed-parameter tractable if and only if it is kernelizable and
64:
A standard example for a kernelization algorithm is the kernelization of the
4519:
Fomin, Fedor V.; Lokshtanov, Daniel; Saurabh, Saket; Zehavi, Meirav (2019),
4454:
4252:
32:
4215:
2611:. To kernelize an input, run this algorithm on the given input for at most
4528:
2905:, it follows that the size of the kernel produced in this way is at most
2654:
steps. If it terminates with an answer, use that answer to select either
4241:
Proceedings of the 42nd ACM Symposium on Theory of
Computing (STOC 2010)
3893:, a different design technique for fixed-parameter tractable algorithms
2315:
is the running time for the algorithm used to solve the kernels. Since
901:
132:
135:. However, the following reduction rules may be used to kernelize it:
3667:
for which some other complexity measure is bounded. For example, the
743:
kernelization algorithms are known that produce kernels with at most
4182:
4111:; Hermelin, Danny (2009), "On problems without polynomial kernels",
4383:
1535:
of kernelization is called a kernel. In this general context, the
2448:, and at least one instance that is not in the language, called
879:
4040:
2411:, this implies that the problem is fixed-parameter tractable.
2130:
Kernelizability and fixed-parameter tractability are equivalent
4051:
2760:
bound on the number of steps without terminating, then return
843:
It is not possible, in this problem, to find a kernel of size
4200:"Vertex cover: Further observations and further improvements"
399:. For, after eliminating all vertices of degree greater than
3919:
This unpublished observation is acknowledged in a paper of
1037:
would have any unlikely complexity-theoretic consequences.
976:
edges. It is unknown for vertex cover whether kernels with
3338:
parametrized by the size of the feedback vertex set: The
1095:{\displaystyle L\subseteq \Sigma ^{*}\times \mathbb {N} }
934:
it is impossible in polynomial time to find kernels with
3903:
a kernel may lose a given factor in the solution quality
2382:
is computable and testing all possible inputs of length
3612:{\displaystyle {\text{coNP}}\subseteq {\text{NP/poly}}}
3525:-path problem is to decide whether a given graph has a
3473:{\displaystyle {\text{coNP}}\subseteq {\text{NP/poly}}}
3325:{\displaystyle {\text{coNP}}\subseteq {\text{NP/poly}}}
3193:{\displaystyle {\text{coNP}}\subseteq {\text{NP/poly}}}
4146:
3974:
3951:
3867:
3847:
3822:
3786:
3761:
3741:
3721:
3697:
3677:
3648:
3595:
3575:
3569:, and it does not have kernels of size polynomial in
3555:
3535:
3511:
3489:
3456:
3414:
3378:
3348:
3308:
3266:
3226:
3206:
3176:
3134:
3108:
3072:
3049:
3004:
2911:
2830:
2798:
2766:
2723:
2693:
2660:
2617:
2588:
2568:
2536:
2484:
2454:
2421:
2388:
2359:
2321:
2292:
2222:
2193:
2147:
2095:
2075:
2033:
2013:
1990:
1970:
1950:
1944:
Note that in this notation, the bound on the size of
1926:
1906:
1886:
1863:
1843:
1823:
1803:
1780:
1760:
1740:
1720:
1684:
1664:
1619:
1586:
1545:
1499:
1475:
1450:
1428:
1408:
1383:
1360:
1318:
1298:
1266:
1221:
1201:
1171:
1139:
1119:
1067:
1017:
982:
940:
914:
887:
849:
826:
788:
749:
725:
705:
685:
665:
645:
587:
549:
522:
492:
465:
445:
425:
405:
385:
358:
335:
315:
292:
271:
251:
231:
211:
191:
171:
145:
117:
97:
77:
4521:
3945:
give a kernel based on the crown reduction that has
2187:
for some c, is invoked to generate a kernel of size
3841:can be transformed into a minimum vertex cover for
2027:is often referred to as the size of the kernel. If
1647:{\displaystyle \kappa :\Sigma ^{*}\to \mathbb {N} }
573:vertices. This kernelization may be implemented in
4159:
3983:
3960:
3873:
3853:
3833:
3808:
3772:
3747:
3727:
3703:
3683:
3654:
3611:
3581:
3561:
3549:. This problem has kernels of size exponential in
3541:
3517:
3495:
3472:
3442:
3408:edges. Furthermore, it does not have kernels with
3400:
3364:
3324:
3294:
3248:
3212:
3192:
3162:
3120:
3094:
3058:
3039:parametrized by the size of the vertex cover: The
3019:
2990:
2897:
2816:
2784:
2752:
2709:
2679:
2646:
2603:
2574:
2554:
2522:
2470:
2440:
2403:
2374:
2345:
2307:
2278:
2208:
2179:
2118:
2081:
2061:
2019:
1996:
1976:
1956:
1932:
1912:
1892:
1869:
1849:
1829:
1809:
1786:
1766:
1746:
1726:
1699:
1670:
1646:
1605:
1556:
1527:
1481:
1461:
1434:
1414:
1394:
1366:
1346:
1304:
1284:
1249:
1207:
1187:
1157:
1125:
1094:
1029:
1003:
968:
926:
893:
870:
832:
812:
758:
731:
711:
691:
671:
651:
631:
565:
535:
504:
478:
451:
431:
411:
391:
371:
341:
321:
298:
277:
257:
237:
217:
197:
177:
157:
123:
103:
83:
4198:Chen, Jianer; Kanj, Iyad A.; Jia, Weijia (2001),
4007:
3991:vertex bound is a bit more involved and folklore.
2353:is computable, e.g. by using the assumption that
679:edges, allowing it to be solved efficiently when
4062:
2912:
2991:{\displaystyle \max\{|I_{yes}|,|I_{no}|,f(k)\}}
419:, each remaining vertex can only cover at most
3638:Kernelization for structural parameterizations
2898:{\displaystyle f(k)\cdot |x|^{c}>|x|^{c+1}}
1774:and maps it in polynomial time to an instance
4085:; Suters, W. Henry; Symons, Chris T. (2004),
3920:
3816:vertices such that a minimum vertex cover in
2824:is only returned as a kernel for inputs with
1054:
68:by S. Buss. In this problem, the input is an
36:the desired output for the original problem.
8:
4402:Lampis, Michael (2011), "A kernel of order 2
4289:, Monographs in Computer Science, Springer,
4231:Dell, Holger; van Melkebeek, Dieter (2010),
2985:
2915:
4523:, Cambridge University Press, p. 528,
4077:Abu-Khzam, Faisal N.; Collins, Rebecca L.;
4018:
2717:as the kernel. If, instead, it exceeds the
2089:admits a polynomial kernel. Similarly, for
3128:, vertex cover does not have kernels with
4481:
4392:
4382:
4151:
4145:
4126:
3973:
3950:
3942:
3931:
3866:
3846:
3821:
3797:
3785:
3760:
3740:
3720:
3696:
3676:
3647:
3604:
3596:
3594:
3574:
3554:
3534:
3510:
3488:
3465:
3457:
3455:
3425:
3413:
3389:
3377:
3356:
3347:
3317:
3309:
3307:
3277:
3265:
3237:
3225:
3205:
3185:
3177:
3175:
3145:
3133:
3107:
3083:
3071:
3048:
3003:
2965:
2956:
2947:
2939:
2927:
2918:
2910:
2883:
2878:
2869:
2860:
2855:
2846:
2829:
2797:
2765:
2738:
2733:
2724:
2722:
2698:
2692:
2665:
2659:
2632:
2627:
2618:
2616:
2587:
2567:
2535:
2514:
2509:
2500:
2483:
2459:
2453:
2426:
2420:
2387:
2358:
2320:
2291:
2267:
2262:
2253:
2221:
2192:
2168:
2163:
2154:
2146:
2102:
2094:
2074:
2044:
2032:
2012:
1989:
1969:
1949:
1925:
1905:
1885:
1862:
1842:
1822:
1802:
1779:
1759:
1739:
1719:
1683:
1663:
1640:
1639:
1630:
1618:
1597:
1585:
1573:
1544:
1498:
1474:
1449:
1427:
1407:
1382:
1359:
1317:
1297:
1265:
1220:
1200:
1180:
1172:
1170:
1138:
1118:
1088:
1087:
1078:
1066:
1016:
981:
951:
939:
913:
886:
848:
825:
787:
768:linear program relaxation of vertex cover
748:
724:
704:
684:
664:
644:
606:
598:
586:
557:
548:
527:
521:
491:
470:
464:
444:
424:
404:
384:
363:
357:
334:
314:
291:
270:
250:
230:
210:
190:
170:
144:
116:
96:
76:
47:. When this is possible, it results in a
4551:Invitation to Fixed-Parameter Algorithms
4473:Invitation to Fixed-Parameter Algorithms
4029:
4114:Journal of Computer and System Sciences
4003:
4001:
3999:
3997:
3912:
3260:, and it does not have kernels of size
1734:is an algorithm that takes an instance
1133:is an algorithm that takes an instance
31:is a technique for designing efficient
4554:, Oxford University Press, Chapter 7,
3220:-uniform hypergraphs has kernels with
1606:{\displaystyle L\subseteq \Sigma ^{*}}
779:
3443:{\displaystyle O(k^{2-\varepsilon })}
3295:{\displaystyle O(k^{d-\varepsilon })}
3163:{\displaystyle O(k^{2-\varepsilon })}
7:
2126:, the problem admits linear kernel.
1900:is bounded by a computable function
1402:is bounded by a computable function
349:cannot be part of any minimal cover.
245:by one. Every vertex cover of size
185:is a vertex of degree greater than
3663:
2279:{\displaystyle g(f(k))+O(|x|^{c})}
1627:
1594:
1165:and maps it in time polynomial in
1075:
969:{\displaystyle O(k^{2-\epsilon })}
459:vertices could only cover at most
14:
4441:kernel for feedback vertex set",
3121:{\displaystyle \varepsilon >0}
3043:problem has kernels with at most
2523:{\displaystyle f(k)\cdot |x|^{c}}
1984:is also bounded by a function in
632:{\displaystyle O(2^{2k^{2}}+n+m)}
111:. The output is a set of at most
3881:are reduced to small instances.
3735:whose feedback vertex number is
3200:. The vertex cover problems in
820:vertices for any fixed constant
4335:Parameterized Complexity Theory
4140:(1993), "Nondeterminism within
4008:Dell & van Melkebeek (2010)
3625:Many parameterized versions of
1580:consists of a decision problem
41:parameterized complexity theory
4583:, Springer, Chapters 2 and 9,
4443:ACM Transactions on Algorithms
4437:Thomassé, Stéphan (2010), "A 4
4417:Information Processing Letters
4063:Jansen & Bodlaender (2013)
3803:
3790:
3437:
3418:
3395:
3382:
3289:
3270:
3243:
3230:
3157:
3138:
3089:
3076:
3014:
3008:
2982:
2976:
2966:
2948:
2940:
2919:
2879:
2870:
2856:
2847:
2840:
2834:
2811:
2799:
2792:itself as the kernel. Because
2779:
2767:
2734:
2725:
2628:
2619:
2598:
2592:
2549:
2537:
2510:
2501:
2494:
2488:
2398:
2392:
2369:
2363:
2340:
2337:
2331:
2325:
2302:
2296:
2273:
2263:
2254:
2250:
2241:
2238:
2232:
2226:
2203:
2197:
2174:
2164:
2155:
2151:
2112:
2106:
2054:
2048:
1964:implies that the parameter of
1694:
1688:
1636:
1522:
1500:
1341:
1319:
1279:
1267:
1244:
1222:
1181:
1173:
1152:
1140:
1030:{\displaystyle \epsilon >0}
1004:{\displaystyle (2-\epsilon )k}
995:
983:
963:
944:
927:{\displaystyle \epsilon >0}
865:
853:
626:
591:
1:
3102:edges. Furthermore, for any
512:, which also has no solution.
1714:for a parameterized problem
1654:, the parameterization. The
1469:is bounded by a function in
1113:for a parameterized problem
225:from the graph and decrease
52:type. This is also true for
4476:, Oxford University Press,
4019:Chen, Kanj & Jia (2001)
3921:Buss & Goldsmith (1993)
1055:Downey & Fellows (1999)
4628:
4470:Niedermeier, Rolf (2006),
4128:10.1016/j.jcss.2009.04.001
2180:{\displaystyle O(|x|^{c})}
2062:{\displaystyle f=k^{O(1)}}
1700:{\displaystyle \kappa (x)}
894:{\displaystyle \subseteq }
813:{\displaystyle 2k-c\log k}
15:
4430:10.1016/j.ipl.2011.09.003
4394:10.1007/s00224-012-9393-4
4295:10.1007/978-1-4612-0515-9
4170:SIAM Journal on Computing
4094:, University of Tennessee
3897:Approximate kernelization
3342:problem has kernels with
2753:{\displaystyle |x|^{c+1}}
2647:{\displaystyle |x|^{c+1}}
871:{\displaystyle O(\log k)}
54:approximate kernelization
49:fixed-parameter tractable
4607:Parameterized complexity
4581:Parameterized Algorithms
4287:Parameterized Complexity
4041:Bodlaender et al. (2009)
3809:{\displaystyle O(k^{3})}
3401:{\displaystyle O(k^{2})}
3249:{\displaystyle O(k^{d})}
3095:{\displaystyle O(k^{2})}
2119:{\displaystyle f={O(k)}}
4455:10.1145/1721837.1721848
4253:10.1145/1806689.1806725
3943:Flum & Grohe (2006)
3932:Flum & Grohe (2006)
3671:of an undirected graph
3623:Bidimensional problems:
2680:{\displaystyle I_{yes}}
2441:{\displaystyle I_{yes}}
2346:{\displaystyle g(f(k))}
1528:{\displaystyle (x',k')}
1347:{\displaystyle (x',k')}
1250:{\displaystyle (x',k')}
1049:Downey–Fellows notation
91:together with a number
4612:Analysis of algorithms
4216:10.1006/jagm.2001.1186
4161:
3985:
3962:
3875:
3855:
3835:
3810:
3774:
3749:
3729:
3705:
3685:
3669:feedback vertex number
3656:
3613:
3583:
3563:
3543:
3519:
3497:
3474:
3444:
3402:
3366:
3365:{\displaystyle 4k^{2}}
3326:
3296:
3250:
3214:
3194:
3164:
3122:
3096:
3060:
3021:
2992:
2899:
2818:
2786:
2754:
2711:
2710:{\displaystyle I_{no}}
2681:
2648:
2605:
2576:
2556:
2524:
2472:
2471:{\displaystyle I_{no}}
2442:
2405:
2376:
2347:
2309:
2280:
2210:
2181:
2120:
2083:
2063:
2021:
1998:
1978:
1958:
1934:
1914:
1894:
1871:
1851:
1831:
1811:
1788:
1768:
1748:
1728:
1701:
1672:
1648:
1607:
1574:Flum & Grohe (2006
1558:
1529:
1483:
1463:
1436:
1416:
1396:
1368:
1348:
1306:
1286:
1251:
1209:
1189:
1159:
1127:
1096:
1031:
1005:
970:
928:
904:(believed unlikely by
895:
872:
834:
814:
760:
733:
713:
693:
673:
653:
633:
567:
566:{\displaystyle 2k^{2}}
537:
506:
480:
453:
433:
413:
393:
373:
343:
323:
300:
279:
259:
239:
219:
199:
179:
159:
158:{\displaystyle k>0}
125:
105:
85:
4529:10.1017/9781107415157
4204:Journal of Algorithms
4162:
4160:{\displaystyle P^{*}}
3986:
3963:
3901:optimization problems
3891:Iterative compression
3876:
3856:
3836:
3811:
3775:
3750:
3730:
3706:
3686:
3657:
3614:
3584:
3564:
3544:
3520:
3498:
3475:
3445:
3403:
3367:
3327:
3297:
3251:
3215:
3195:
3165:
3123:
3097:
3061:
3022:
2993:
2900:
2819:
2817:{\displaystyle (x,k)}
2787:
2785:{\displaystyle (x,k)}
2755:
2712:
2682:
2649:
2606:
2577:
2557:
2555:{\displaystyle (x,k)}
2525:
2473:
2443:
2406:
2377:
2348:
2310:
2281:
2211:
2182:
2121:
2084:
2064:
2022:
1999:
1979:
1959:
1935:
1915:
1895:
1872:
1852:
1832:
1812:
1789:
1769:
1749:
1729:
1702:
1673:
1649:
1608:
1578:parameterized problem
1559:
1530:
1484:
1464:
1437:
1417:
1397:
1369:
1349:
1307:
1287:
1285:{\displaystyle (x,k)}
1252:
1210:
1190:
1160:
1158:{\displaystyle (x,k)}
1128:
1097:
1059:parameterized problem
1032:
1006:
971:
929:
896:
873:
835:
815:
761:
734:
714:
694:
674:
654:
634:
568:
538:
536:{\displaystyle k^{2}}
507:
481:
479:{\displaystyle k^{2}}
454:
434:
414:
394:
374:
372:{\displaystyle k^{2}}
344:
324:
301:
280:
260:
240:
220:
200:
180:
160:
126:
106:
86:
60:Example: vertex cover
4424:(23–24): 1089–1091,
4371:Theory Comput. Syst.
4247:, pp. 251–260,
4144:
4083:Langston, Michael A.
3972:
3949:
3865:
3845:
3820:
3784:
3759:
3739:
3719:
3695:
3675:
3646:
3642:While the parameter
3593:
3573:
3553:
3533:
3509:
3487:
3454:
3412:
3376:
3346:
3306:
3264:
3224:
3204:
3174:
3132:
3106:
3070:
3047:
3020:{\displaystyle f(k)}
3002:
2909:
2828:
2796:
2764:
2721:
2691:
2658:
2615:
2604:{\displaystyle f(k)}
2586:
2566:
2562:, for some constant
2534:
2482:
2452:
2419:
2404:{\displaystyle f(k)}
2386:
2375:{\displaystyle f(k)}
2357:
2319:
2308:{\displaystyle g(n)}
2290:
2220:
2209:{\displaystyle f(k)}
2191:
2145:
2093:
2073:
2031:
2011:
1988:
1968:
1948:
1924:
1904:
1884:
1861:
1841:
1821:
1801:
1778:
1758:
1738:
1718:
1682:
1662:
1617:
1584:
1543:
1497:
1473:
1448:
1426:
1406:
1381:
1358:
1316:
1296:
1264:
1219:
1199:
1169:
1137:
1117:
1065:
1015:
980:
938:
912:
906:complexity theorists
885:
847:
824:
786:
747:
723:
703:
683:
663:
643:
585:
547:
520:
490:
463:
443:
423:
403:
383:
356:
333:
313:
290:
269:
249:
229:
209:
189:
169:
143:
115:
95:
75:
66:vertex cover problem
4414:for vertex cover",
4406: −
4136:Buss, Jonathan F.;
4109:Fellows, Michael R.
4101:Bodlaender, Hans L.
4079:Fellows, Michael R.
4052:Fomin et al. (2010)
3529:of length at least
3340:feedback vertex set
3336:Feedback vertex set
2530:steps on instances
1572:In the notation of
1568:Flum–Grohe notation
1188:{\displaystyle |x|}
1053:In the notation of
505:{\displaystyle k=0}
439:edges and a set of
4363:, pp. 503–510
4157:
3984:{\displaystyle 2k}
3981:
3961:{\displaystyle 3k}
3958:
3871:
3851:
3834:{\displaystyle G'}
3831:
3806:
3773:{\displaystyle G'}
3770:
3755:, outputs a graph
3745:
3725:
3701:
3681:
3652:
3609:
3579:
3559:
3539:
3515:
3493:
3470:
3440:
3398:
3362:
3322:
3292:
3246:
3210:
3190:
3160:
3118:
3092:
3059:{\displaystyle 2k}
3056:
3017:
2988:
2895:
2814:
2782:
2750:
2707:
2677:
2644:
2601:
2582:and some function
2572:
2552:
2520:
2468:
2438:
2401:
2372:
2343:
2305:
2276:
2206:
2177:
2116:
2079:
2069:, it is said that
2059:
2017:
1994:
1974:
1954:
1930:
1910:
1890:
1867:
1847:
1827:
1807:
1784:
1764:
1744:
1724:
1697:
1668:
1644:
1603:
1557:{\displaystyle x'}
1554:
1525:
1479:
1462:{\displaystyle k'}
1459:
1432:
1412:
1395:{\displaystyle x'}
1392:
1364:
1344:
1302:
1282:
1247:
1205:
1185:
1155:
1123:
1092:
1027:
1011:vertices for some
1001:
966:
924:
891:
868:
830:
810:
759:{\displaystyle 2k}
756:
729:
709:
689:
669:
649:
629:
579:brute force search
563:
533:
502:
476:
449:
429:
409:
389:
369:
339:
319:
306:back to the cover.
296:
275:
255:
235:
215:
195:
175:
155:
121:
101:
81:
4590:978-3-319-21274-6
4546:Niedermeier, Rolf
4345:978-3-540-29952-3
4262:978-1-4503-0050-6
3874:{\displaystyle k}
3854:{\displaystyle G}
3748:{\displaystyle k}
3728:{\displaystyle G}
3704:{\displaystyle G}
3684:{\displaystyle G}
3655:{\displaystyle k}
3607:
3599:
3582:{\displaystyle k}
3562:{\displaystyle k}
3542:{\displaystyle k}
3518:{\displaystyle k}
3496:{\displaystyle k}
3468:
3460:
3320:
3312:
3213:{\displaystyle d}
3188:
3180:
2575:{\displaystyle c}
2082:{\displaystyle L}
2020:{\displaystyle f}
1997:{\displaystyle k}
1977:{\displaystyle y}
1957:{\displaystyle y}
1933:{\displaystyle k}
1913:{\displaystyle f}
1893:{\displaystyle y}
1870:{\displaystyle L}
1850:{\displaystyle y}
1830:{\displaystyle L}
1810:{\displaystyle x}
1787:{\displaystyle y}
1767:{\displaystyle k}
1747:{\displaystyle x}
1727:{\displaystyle L}
1671:{\displaystyle x}
1482:{\displaystyle k}
1435:{\displaystyle k}
1415:{\displaystyle f}
1367:{\displaystyle L}
1305:{\displaystyle L}
1208:{\displaystyle k}
1126:{\displaystyle L}
833:{\displaystyle c}
732:{\displaystyle m}
712:{\displaystyle n}
699:is small even if
692:{\displaystyle k}
672:{\displaystyle m}
652:{\displaystyle n}
639:for a graph with
452:{\displaystyle k}
432:{\displaystyle k}
412:{\displaystyle k}
392:{\displaystyle k}
342:{\displaystyle v}
322:{\displaystyle v}
299:{\displaystyle v}
278:{\displaystyle v}
258:{\displaystyle k}
238:{\displaystyle k}
218:{\displaystyle v}
198:{\displaystyle k}
178:{\displaystyle v}
124:{\displaystyle k}
104:{\displaystyle k}
84:{\displaystyle G}
4619:
4593:
4575:
4574:
4573:
4564:, archived from
4541:
4507:
4506:
4505:
4496:, archived from
4485:
4465:
4432:
4397:
4396:
4386:
4364:
4354:
4353:
4352:
4323:
4273:
4246:
4237:
4226:
4193:
4166:
4164:
4163:
4158:
4156:
4155:
4131:
4130:
4095:
4093:
4065:
4060:
4054:
4049:
4043:
4038:
4032:
4027:
4021:
4016:
4010:
4005:
3992:
3990:
3988:
3987:
3982:
3967:
3965:
3964:
3959:
3940:
3934:
3929:
3923:
3917:
3880:
3878:
3877:
3872:
3860:
3858:
3857:
3852:
3840:
3838:
3837:
3832:
3830:
3815:
3813:
3812:
3807:
3802:
3801:
3779:
3777:
3776:
3771:
3769:
3754:
3752:
3751:
3746:
3734:
3732:
3731:
3726:
3710:
3708:
3707:
3702:
3690:
3688:
3687:
3682:
3661:
3659:
3658:
3653:
3618:
3616:
3615:
3610:
3608:
3605:
3600:
3597:
3588:
3586:
3585:
3580:
3568:
3566:
3565:
3560:
3548:
3546:
3545:
3540:
3524:
3522:
3521:
3516:
3502:
3500:
3499:
3494:
3479:
3477:
3476:
3471:
3469:
3466:
3461:
3458:
3449:
3447:
3446:
3441:
3436:
3435:
3407:
3405:
3404:
3399:
3394:
3393:
3371:
3369:
3368:
3363:
3361:
3360:
3331:
3329:
3328:
3323:
3321:
3318:
3313:
3310:
3301:
3299:
3298:
3293:
3288:
3287:
3256:edges using the
3255:
3253:
3252:
3247:
3242:
3241:
3219:
3217:
3216:
3211:
3199:
3197:
3196:
3191:
3189:
3186:
3181:
3178:
3169:
3167:
3166:
3161:
3156:
3155:
3127:
3125:
3124:
3119:
3101:
3099:
3098:
3093:
3088:
3087:
3065:
3063:
3062:
3057:
3026:
3024:
3023:
3018:
2997:
2995:
2994:
2989:
2969:
2964:
2963:
2951:
2943:
2938:
2937:
2922:
2904:
2902:
2901:
2896:
2894:
2893:
2882:
2873:
2865:
2864:
2859:
2850:
2823:
2821:
2820:
2815:
2791:
2789:
2788:
2783:
2759:
2757:
2756:
2751:
2749:
2748:
2737:
2728:
2716:
2714:
2713:
2708:
2706:
2705:
2686:
2684:
2683:
2678:
2676:
2675:
2653:
2651:
2650:
2645:
2643:
2642:
2631:
2622:
2610:
2608:
2607:
2602:
2581:
2579:
2578:
2573:
2561:
2559:
2558:
2553:
2529:
2527:
2526:
2521:
2519:
2518:
2513:
2504:
2477:
2475:
2474:
2469:
2467:
2466:
2447:
2445:
2444:
2439:
2437:
2436:
2410:
2408:
2407:
2402:
2381:
2379:
2378:
2373:
2352:
2350:
2349:
2344:
2314:
2312:
2311:
2306:
2285:
2283:
2282:
2277:
2272:
2271:
2266:
2257:
2215:
2213:
2212:
2207:
2186:
2184:
2183:
2178:
2173:
2172:
2167:
2158:
2125:
2123:
2122:
2117:
2115:
2088:
2086:
2085:
2080:
2068:
2066:
2065:
2060:
2058:
2057:
2026:
2024:
2023:
2018:
2003:
2001:
2000:
1995:
1983:
1981:
1980:
1975:
1963:
1961:
1960:
1955:
1939:
1937:
1936:
1931:
1919:
1917:
1916:
1911:
1899:
1897:
1896:
1891:
1876:
1874:
1873:
1868:
1856:
1854:
1853:
1848:
1836:
1834:
1833:
1828:
1816:
1814:
1813:
1808:
1793:
1791:
1790:
1785:
1773:
1771:
1770:
1765:
1753:
1751:
1750:
1745:
1733:
1731:
1730:
1725:
1706:
1704:
1703:
1698:
1677:
1675:
1674:
1669:
1653:
1651:
1650:
1645:
1643:
1635:
1634:
1612:
1610:
1609:
1604:
1602:
1601:
1576:, p. 4), a
1563:
1561:
1560:
1555:
1553:
1534:
1532:
1531:
1526:
1521:
1510:
1488:
1486:
1485:
1480:
1468:
1466:
1465:
1460:
1458:
1441:
1439:
1438:
1433:
1421:
1419:
1418:
1413:
1401:
1399:
1398:
1393:
1391:
1373:
1371:
1370:
1365:
1353:
1351:
1350:
1345:
1340:
1329:
1311:
1309:
1308:
1303:
1291:
1289:
1288:
1283:
1256:
1254:
1253:
1248:
1243:
1232:
1214:
1212:
1211:
1206:
1194:
1192:
1191:
1186:
1184:
1176:
1164:
1162:
1161:
1156:
1132:
1130:
1129:
1124:
1104:decision problem
1101:
1099:
1098:
1093:
1091:
1083:
1082:
1036:
1034:
1033:
1028:
1010:
1008:
1007:
1002:
975:
973:
972:
967:
962:
961:
933:
931:
930:
925:
900:
898:
897:
892:
877:
875:
874:
869:
839:
837:
836:
831:
819:
817:
816:
811:
776:alternating path
765:
763:
762:
757:
739:are both large.
738:
736:
735:
730:
718:
716:
715:
710:
698:
696:
695:
690:
678:
676:
675:
670:
658:
656:
655:
650:
638:
636:
635:
630:
613:
612:
611:
610:
572:
570:
569:
564:
562:
561:
542:
540:
539:
534:
532:
531:
511:
509:
508:
503:
485:
483:
482:
477:
475:
474:
458:
456:
455:
450:
438:
436:
435:
430:
418:
416:
415:
410:
398:
396:
395:
390:
378:
376:
375:
370:
368:
367:
348:
346:
345:
340:
328:
326:
325:
320:
305:
303:
302:
297:
284:
282:
281:
276:
264:
262:
261:
256:
244:
242:
241:
236:
224:
222:
221:
216:
204:
202:
201:
196:
184:
182:
181:
176:
164:
162:
161:
156:
130:
128:
127:
122:
110:
108:
107:
102:
90:
88:
87:
82:
70:undirected graph
25:computer science
4627:
4626:
4622:
4621:
4620:
4618:
4617:
4616:
4597:
4596:
4591:
4578:
4571:
4569:
4562:
4544:
4539:
4518:
4515:
4513:Further reading
4503:
4501:
4494:
4469:
4436:
4410: log
4401:
4368:
4358:
4350:
4348:
4346:
4327:
4305:
4277:
4263:
4244:
4235:
4230:
4197:
4183:10.1137/0222038
4147:
4142:
4141:
4138:Goldsmith, Judy
4135:
4099:
4091:
4076:
4073:
4068:
4061:
4057:
4050:
4046:
4039:
4035:
4030:Thomassé (2010)
4028:
4024:
4017:
4013:
4006:
3995:
3970:
3969:
3947:
3946:
3941:
3937:
3930:
3926:
3918:
3914:
3910:
3887:
3863:
3862:
3843:
3842:
3823:
3818:
3817:
3793:
3782:
3781:
3762:
3757:
3756:
3737:
3736:
3717:
3716:
3693:
3692:
3673:
3672:
3644:
3643:
3640:
3591:
3590:
3571:
3570:
3551:
3550:
3531:
3530:
3507:
3506:
3485:
3484:
3452:
3451:
3421:
3410:
3409:
3385:
3374:
3373:
3352:
3344:
3343:
3304:
3303:
3273:
3262:
3261:
3258:sunflower lemma
3233:
3222:
3221:
3202:
3201:
3172:
3171:
3141:
3130:
3129:
3104:
3103:
3079:
3068:
3067:
3045:
3044:
3033:
3027:is computable.
3000:
2999:
2952:
2923:
2907:
2906:
2877:
2854:
2826:
2825:
2794:
2793:
2762:
2761:
2732:
2719:
2718:
2694:
2689:
2688:
2661:
2656:
2655:
2626:
2613:
2612:
2584:
2583:
2564:
2563:
2532:
2531:
2508:
2480:
2479:
2455:
2450:
2449:
2422:
2417:
2416:
2384:
2383:
2355:
2354:
2317:
2316:
2288:
2287:
2261:
2218:
2217:
2189:
2188:
2162:
2143:
2142:
2132:
2091:
2090:
2071:
2070:
2040:
2029:
2028:
2009:
2008:
1986:
1985:
1966:
1965:
1946:
1945:
1922:
1921:
1902:
1901:
1882:
1881:
1859:
1858:
1839:
1838:
1837:if and only if
1819:
1818:
1799:
1798:
1776:
1775:
1756:
1755:
1754:with parameter
1736:
1735:
1716:
1715:
1680:
1679:
1660:
1659:
1658:of an instance
1626:
1615:
1614:
1613:and a function
1593:
1582:
1581:
1570:
1546:
1541:
1540:
1514:
1503:
1495:
1494:
1471:
1470:
1451:
1446:
1445:
1424:
1423:
1404:
1403:
1384:
1379:
1378:
1356:
1355:
1333:
1322:
1314:
1313:
1312:if and only if
1294:
1293:
1262:
1261:
1236:
1225:
1217:
1216:
1215:to an instance
1197:
1196:
1167:
1166:
1135:
1134:
1115:
1114:
1074:
1063:
1062:
1051:
1043:
1013:
1012:
978:
977:
947:
936:
935:
910:
909:
883:
882:
845:
844:
822:
821:
784:
783:
745:
744:
721:
720:
701:
700:
681:
680:
661:
660:
641:
640:
602:
594:
583:
582:
553:
545:
544:
523:
518:
517:
488:
487:
466:
461:
460:
441:
440:
421:
420:
401:
400:
381:
380:
359:
354:
353:
331:
330:
311:
310:
288:
287:
267:
266:
247:
246:
227:
226:
207:
206:
187:
186:
167:
166:
141:
140:
113:
112:
93:
92:
73:
72:
62:
45:polynomial time
21:
12:
11:
5:
4625:
4623:
4615:
4614:
4609:
4599:
4598:
4595:
4594:
4589:
4576:
4560:
4542:
4538:978-1107057760
4537:
4514:
4511:
4510:
4509:
4492:
4467:
4434:
4399:
4377:(2): 263–299,
4366:
4356:
4344:
4325:
4303:
4283:Fellows, M. R.
4275:
4261:
4228:
4210:(2): 280–301,
4195:
4177:(3): 560–572,
4154:
4150:
4133:
4121:(8): 423–434,
4105:Downey, Rod G.
4097:
4072:
4069:
4067:
4066:
4055:
4044:
4033:
4022:
4011:
3993:
3980:
3977:
3968:vertices. The
3957:
3954:
3935:
3924:
3911:
3909:
3906:
3905:
3904:
3894:
3886:
3883:
3870:
3850:
3829:
3826:
3805:
3800:
3796:
3792:
3789:
3768:
3765:
3744:
3724:
3700:
3680:
3651:
3639:
3636:
3635:
3634:
3620:
3603:
3578:
3558:
3538:
3514:
3492:
3481:
3464:
3439:
3434:
3431:
3428:
3424:
3420:
3417:
3397:
3392:
3388:
3384:
3381:
3359:
3355:
3351:
3333:
3316:
3291:
3286:
3283:
3280:
3276:
3272:
3269:
3245:
3240:
3236:
3232:
3229:
3209:
3184:
3159:
3154:
3151:
3148:
3144:
3140:
3137:
3117:
3114:
3111:
3091:
3086:
3082:
3078:
3075:
3055:
3052:
3032:
3029:
3016:
3013:
3010:
3007:
2987:
2984:
2981:
2978:
2975:
2972:
2968:
2962:
2959:
2955:
2950:
2946:
2942:
2936:
2933:
2930:
2926:
2921:
2917:
2914:
2892:
2889:
2886:
2881:
2876:
2872:
2868:
2863:
2858:
2853:
2849:
2845:
2842:
2839:
2836:
2833:
2813:
2810:
2807:
2804:
2801:
2781:
2778:
2775:
2772:
2769:
2747:
2744:
2741:
2736:
2731:
2727:
2704:
2701:
2697:
2674:
2671:
2668:
2664:
2641:
2638:
2635:
2630:
2625:
2621:
2600:
2597:
2594:
2591:
2571:
2551:
2548:
2545:
2542:
2539:
2517:
2512:
2507:
2503:
2499:
2496:
2493:
2490:
2487:
2465:
2462:
2458:
2435:
2432:
2429:
2425:
2400:
2397:
2394:
2391:
2371:
2368:
2365:
2362:
2342:
2339:
2336:
2333:
2330:
2327:
2324:
2304:
2301:
2298:
2295:
2275:
2270:
2265:
2260:
2256:
2252:
2249:
2246:
2243:
2240:
2237:
2234:
2231:
2228:
2225:
2205:
2202:
2199:
2196:
2176:
2171:
2166:
2161:
2157:
2153:
2150:
2131:
2128:
2114:
2111:
2108:
2105:
2101:
2098:
2078:
2056:
2053:
2050:
2047:
2043:
2039:
2036:
2016:
1993:
1973:
1953:
1942:
1941:
1929:
1909:
1889:
1878:
1866:
1846:
1826:
1806:
1783:
1763:
1743:
1723:
1696:
1693:
1690:
1687:
1678:is the number
1667:
1642:
1638:
1633:
1629:
1625:
1622:
1600:
1596:
1592:
1589:
1569:
1566:
1552:
1549:
1539:of the string
1524:
1520:
1517:
1513:
1509:
1506:
1502:
1491:
1490:
1478:
1457:
1454:
1443:
1431:
1411:
1390:
1387:
1375:
1363:
1343:
1339:
1336:
1332:
1328:
1325:
1321:
1301:
1281:
1278:
1275:
1272:
1269:
1246:
1242:
1239:
1235:
1231:
1228:
1224:
1204:
1183:
1179:
1175:
1154:
1151:
1148:
1145:
1142:
1122:
1090:
1086:
1081:
1077:
1073:
1070:
1050:
1047:
1042:
1039:
1026:
1023:
1020:
1000:
997:
994:
991:
988:
985:
965:
960:
957:
954:
950:
946:
943:
923:
920:
917:
890:
867:
864:
861:
858:
855:
852:
829:
809:
806:
803:
800:
797:
794:
791:
755:
752:
728:
708:
688:
668:
648:
628:
625:
622:
619:
616:
609:
605:
601:
597:
593:
590:
560:
556:
552:
530:
526:
514:
513:
501:
498:
495:
473:
469:
448:
428:
408:
388:
366:
362:
350:
338:
318:
307:
295:
274:
254:
234:
214:
194:
174:
154:
151:
148:
120:
100:
80:
61:
58:
13:
10:
9:
6:
4:
3:
2:
4624:
4613:
4610:
4608:
4605:
4604:
4602:
4592:
4586:
4582:
4577:
4568:on 2007-09-29
4567:
4563:
4561:0-19-856607-7
4557:
4553:
4552:
4547:
4543:
4540:
4534:
4530:
4526:
4522:
4517:
4516:
4512:
4500:on 2008-09-24
4499:
4495:
4493:0-19-856607-7
4489:
4484:
4483:10.1.1.2.9618
4479:
4475:
4474:
4468:
4464:
4460:
4456:
4452:
4448:
4444:
4440:
4435:
4431:
4427:
4423:
4419:
4418:
4413:
4409:
4405:
4400:
4395:
4390:
4385:
4380:
4376:
4372:
4367:
4362:
4357:
4347:
4341:
4337:
4336:
4331:
4330:Grohe, Martin
4326:
4322:
4318:
4314:
4310:
4306:
4304:0-387-94883-X
4300:
4296:
4292:
4288:
4284:
4280:
4279:Downey, R. G.
4276:
4272:
4268:
4264:
4258:
4254:
4250:
4243:
4242:
4234:
4229:
4225:
4221:
4217:
4213:
4209:
4205:
4201:
4196:
4192:
4188:
4184:
4180:
4176:
4172:
4171:
4152:
4148:
4139:
4134:
4129:
4124:
4120:
4116:
4115:
4110:
4106:
4102:
4098:
4090:
4089:
4084:
4080:
4075:
4074:
4070:
4064:
4059:
4056:
4053:
4048:
4045:
4042:
4037:
4034:
4031:
4026:
4023:
4020:
4015:
4012:
4009:
4004:
4002:
4000:
3998:
3994:
3978:
3975:
3955:
3952:
3944:
3939:
3936:
3933:
3928:
3925:
3922:
3916:
3913:
3907:
3902:
3898:
3895:
3892:
3889:
3888:
3884:
3882:
3868:
3848:
3827:
3824:
3798:
3794:
3787:
3766:
3763:
3742:
3722:
3714:
3711:acyclic. The
3698:
3678:
3670:
3665:
3649:
3637:
3632:
3628:
3627:bidimensional
3624:
3621:
3601:
3576:
3556:
3536:
3528:
3512:
3504:
3490:
3482:
3462:
3450:edges unless
3432:
3429:
3426:
3422:
3415:
3390:
3386:
3379:
3372:vertices and
3357:
3353:
3349:
3341:
3337:
3334:
3314:
3284:
3281:
3278:
3274:
3267:
3259:
3238:
3234:
3227:
3207:
3182:
3170:edges unless
3152:
3149:
3146:
3142:
3135:
3115:
3112:
3109:
3084:
3080:
3073:
3066:vertices and
3053:
3050:
3042:
3038:
3035:
3034:
3031:More examples
3030:
3028:
3011:
3005:
2979:
2973:
2970:
2960:
2957:
2953:
2944:
2934:
2931:
2928:
2924:
2890:
2887:
2884:
2874:
2866:
2861:
2851:
2843:
2837:
2831:
2808:
2805:
2802:
2776:
2773:
2770:
2745:
2742:
2739:
2729:
2702:
2699:
2695:
2672:
2669:
2666:
2662:
2639:
2636:
2633:
2623:
2595:
2589:
2569:
2546:
2543:
2540:
2515:
2505:
2497:
2491:
2485:
2463:
2460:
2456:
2433:
2430:
2427:
2423:
2412:
2395:
2389:
2366:
2360:
2334:
2328:
2322:
2299:
2293:
2268:
2258:
2247:
2244:
2235:
2229:
2223:
2200:
2194:
2169:
2159:
2148:
2139:
2137:
2129:
2127:
2109:
2103:
2099:
2096:
2076:
2051:
2045:
2041:
2037:
2034:
2014:
2007:The function
2005:
1991:
1971:
1951:
1927:
1907:
1887:
1879:
1864:
1844:
1824:
1804:
1797:
1796:
1795:
1781:
1761:
1741:
1721:
1713:
1712:kernelization
1708:
1691:
1685:
1665:
1657:
1631:
1623:
1620:
1598:
1590:
1587:
1579:
1575:
1567:
1565:
1550:
1547:
1538:
1518:
1515:
1511:
1507:
1504:
1476:
1455:
1452:
1444:
1429:
1409:
1388:
1385:
1376:
1361:
1337:
1334:
1330:
1326:
1323:
1299:
1276:
1273:
1270:
1260:
1259:
1258:
1240:
1237:
1233:
1229:
1226:
1202:
1177:
1149:
1146:
1143:
1120:
1112:
1111:kernelization
1107:
1105:
1102:describing a
1084:
1079:
1071:
1068:
1060:
1056:
1048:
1046:
1040:
1038:
1024:
1021:
1018:
998:
992:
989:
986:
958:
955:
952:
948:
941:
921:
918:
915:
908:), for every
907:
903:
888:
881:
862:
859:
856:
850:
841:
827:
807:
804:
801:
798:
795:
792:
789:
782:and achieves
781:
780:Lampis (2011)
777:
773:
769:
753:
750:
740:
726:
706:
686:
666:
659:vertices and
646:
623:
620:
617:
614:
607:
603:
599:
595:
588:
580:
576:
558:
554:
550:
528:
524:
499:
496:
493:
471:
467:
446:
426:
406:
386:
364:
360:
352:If more than
351:
336:
316:
308:
293:
272:
265:must contain
252:
232:
212:
192:
172:
152:
149:
146:
138:
137:
136:
134:
118:
98:
78:
71:
67:
59:
57:
55:
50:
46:
42:
37:
34:
30:
29:kernelization
26:
19:
18:Kernel method
4580:
4570:, retrieved
4566:the original
4550:
4520:
4502:, retrieved
4498:the original
4472:
4446:
4442:
4438:
4421:
4415:
4411:
4407:
4403:
4374:
4370:
4360:
4349:, retrieved
4338:, Springer,
4334:
4328:Flum, Jörg;
4286:
4240:
4207:
4203:
4174:
4168:
4118:
4112:
4087:
4058:
4047:
4036:
4025:
4014:
3938:
3927:
3915:
3713:vertex cover
3668:
3641:
3622:
3483:
3335:
3041:vertex cover
3037:Vertex cover
3036:
2413:
2140:
2133:
2006:
1943:
1880:the size of
1711:
1709:
1655:
1577:
1571:
1536:
1492:
1377:the size of
1110:
1108:
1061:is a subset
1058:
1052:
1044:
842:
741:
515:
63:
38:
28:
22:
1493:The output
575:linear time
4601:Categories
4572:2017-06-01
4504:2017-06-01
4449:(2): 1–8,
4351:2010-03-05
4071:References
1794:such that
1257:such that
1041:Definition
33:algorithms
4478:CiteSeerX
4384:1012.4701
4153:∗
3602:⊆
3463:⊆
3433:ε
3430:−
3315:⊆
3285:ε
3282:−
3183:⊆
3153:ε
3150:−
3110:ε
2844:⋅
2498:⋅
2136:decidable
1686:κ
1656:parameter
1637:→
1632:∗
1628:Σ
1621:κ
1599:∗
1595:Σ
1591:⊆
1085:×
1080:∗
1076:Σ
1072:⊆
1019:ϵ
993:ϵ
990:−
959:ϵ
956:−
916:ϵ
889:⊆
860:
805:
796:−
772:Nemhauser
205:, remove
4548:(2006),
4332:(2006),
4321:15271852
4285:(1999),
4224:13557005
4191:43081484
3885:See also
3828:′
3767:′
3664:examples
2286:, where
1551:′
1519:′
1508:′
1456:′
1389:′
1338:′
1327:′
1241:′
1230:′
4463:7510317
4313:1656112
4271:1117711
3662:in the
3606:NP/poly
3589:unless
3467:NP/poly
3319:NP/poly
3302:unless
3187:NP/poly
902:NP/poly
770:due to
133:NP-hard
4587:
4558:
4535:
4490:
4480:
4461:
4342:
4319:
4311:
4301:
4269:
4259:
4222:
4189:
3899:, for
3503:-path:
1857:is in
1817:is in
1354:is in
1292:is in
4459:S2CID
4379:arXiv
4317:S2CID
4267:S2CID
4245:(PDF)
4236:(PDF)
4220:S2CID
4187:S2CID
4092:(PDF)
3908:Notes
3631:minor
1442:, and
4585:ISBN
4556:ISBN
4533:ISBN
4488:ISBN
4340:ISBN
4299:ISBN
4257:ISBN
3598:coNP
3527:path
3505:The
3459:coNP
3311:coNP
3179:coNP
3113:>
2867:>
1537:size
1195:and
1057:, a
1022:>
919:>
880:coNP
719:and
165:and
150:>
27:, a
4525:doi
4451:doi
4426:doi
4422:111
4389:doi
4291:doi
4249:doi
4212:doi
4179:doi
4167:",
4123:doi
3780:on
2913:max
2687:or
1920:in
1877:and
1422:in
857:log
802:log
309:If
139:If
23:In
4603::
4531:,
4486:,
4457:,
4445:,
4420:,
4387:,
4375:53
4373:,
4315:,
4309:MR
4307:,
4297:,
4281:;
4265:,
4255:,
4238:,
4218:,
4208:41
4206:,
4202:,
4185:,
4175:22
4173:,
4119:75
4117:,
4107:;
4103:;
4081:;
3996:^
2138:.
2004:.
1710:A
1707:.
1109:A
1106:.
840:.
56:.
4527::
4508:.
4466:.
4453::
4447:6
4439:k
4433:.
4428::
4412:k
4408:c
4404:k
4398:,
4391::
4381::
4365:.
4355:.
4324:.
4293::
4274:.
4251::
4227:.
4214::
4194:.
4181::
4149:P
4132:.
4125::
4096:.
3979:k
3976:2
3956:k
3953:3
3869:k
3849:G
3825:G
3804:)
3799:3
3795:k
3791:(
3788:O
3764:G
3743:k
3723:G
3699:G
3679:G
3650:k
3633:.
3619:.
3577:k
3557:k
3537:k
3513:k
3491:k
3480:.
3438:)
3427:2
3423:k
3419:(
3416:O
3396:)
3391:2
3387:k
3383:(
3380:O
3358:2
3354:k
3350:4
3332:.
3290:)
3279:d
3275:k
3271:(
3268:O
3244:)
3239:d
3235:k
3231:(
3228:O
3208:d
3158:)
3147:2
3143:k
3139:(
3136:O
3116:0
3090:)
3085:2
3081:k
3077:(
3074:O
3054:k
3051:2
3015:)
3012:k
3009:(
3006:f
2986:}
2983:)
2980:k
2977:(
2974:f
2971:,
2967:|
2961:o
2958:n
2954:I
2949:|
2945:,
2941:|
2935:s
2932:e
2929:y
2925:I
2920:|
2916:{
2891:1
2888:+
2885:c
2880:|
2875:x
2871:|
2862:c
2857:|
2852:x
2848:|
2841:)
2838:k
2835:(
2832:f
2812:)
2809:k
2806:,
2803:x
2800:(
2780:)
2777:k
2774:,
2771:x
2768:(
2746:1
2743:+
2740:c
2735:|
2730:x
2726:|
2703:o
2700:n
2696:I
2673:s
2670:e
2667:y
2663:I
2640:1
2637:+
2634:c
2629:|
2624:x
2620:|
2599:)
2596:k
2593:(
2590:f
2570:c
2550:)
2547:k
2544:,
2541:x
2538:(
2516:c
2511:|
2506:x
2502:|
2495:)
2492:k
2489:(
2486:f
2464:o
2461:n
2457:I
2434:s
2431:e
2428:y
2424:I
2399:)
2396:k
2393:(
2390:f
2370:)
2367:k
2364:(
2361:f
2341:)
2338:)
2335:k
2332:(
2329:f
2326:(
2323:g
2303:)
2300:n
2297:(
2294:g
2274:)
2269:c
2264:|
2259:x
2255:|
2251:(
2248:O
2245:+
2242:)
2239:)
2236:k
2233:(
2230:f
2227:(
2224:g
2204:)
2201:k
2198:(
2195:f
2175:)
2170:c
2165:|
2160:x
2156:|
2152:(
2149:O
2113:)
2110:k
2107:(
2104:O
2100:=
2097:f
2077:L
2055:)
2052:1
2049:(
2046:O
2042:k
2038:=
2035:f
2015:f
1992:k
1972:y
1952:y
1940:.
1928:k
1908:f
1888:y
1865:L
1845:y
1825:L
1805:x
1782:y
1762:k
1742:x
1722:L
1695:)
1692:x
1689:(
1666:x
1641:N
1624::
1588:L
1548:x
1523:)
1516:k
1512:,
1505:x
1501:(
1489:.
1477:k
1453:k
1430:k
1410:f
1386:x
1374:,
1362:L
1342:)
1335:k
1331:,
1324:x
1320:(
1300:L
1280:)
1277:k
1274:,
1271:x
1268:(
1245:)
1238:k
1234:,
1227:x
1223:(
1203:k
1182:|
1178:x
1174:|
1153:)
1150:k
1147:,
1144:x
1141:(
1121:L
1089:N
1069:L
1025:0
999:k
996:)
987:2
984:(
964:)
953:2
949:k
945:(
942:O
922:0
866:)
863:k
854:(
851:O
828:c
808:k
799:c
793:k
790:2
754:k
751:2
727:m
707:n
687:k
667:m
647:n
627:)
624:m
621:+
618:n
615:+
608:2
604:k
600:2
596:2
592:(
589:O
559:2
555:k
551:2
529:2
525:k
500:0
497:=
494:k
472:2
468:k
447:k
427:k
407:k
387:k
365:2
361:k
337:v
317:v
294:v
273:v
253:k
233:k
213:v
193:k
173:v
153:0
147:k
119:k
99:k
79:G
20:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.