2471:
2462:
polynomial, in the sense that each "slice" of fixed k has a polynomial algorithm, although possibly with a different exponent for each k. Compare this with FPT, which merely allows a different constant prefactor for each value of k. XP contains FPT, and it is known that this containment is strict by
151:, the parameter can be the number of vertices in the cover. In many applications, for example when modelling error correction, one can assume the parameter to be "small" compared to the total input size. Then it is challenging to find an algorithm that is exponential
105:(so in particular super-polynomial) in the total size of the input. However, some problems can be solved by algorithms that are exponential only in the size of a fixed parameter while polynomial in the size of the input. Such an algorithm is called a
1238:
is the largest number of logical units with fan-in greater than two on any path from an input to the output. The total number of logical units on the paths (known as depth) must be limited by a constant that holds for all instances of the problem.
921:
is a preprocessing technique that reduces the original instance to its "hard kernel", a possibly much smaller instance that is equivalent to the original instance but has a size that is bounded by a function in the parameter.
58:
problems on a finer scale than in the classical setting, where the complexity of a problem is only measured as a function of the number of bits in the input. This appears to have been first demonstrated in
540:, but the definition admits functions that grow even faster. This is essential for a large part of the early history of this class. The crucial part of the definition is to exclude functions of the form
213:
2610:
2338:
2785:
2644:
3101:
2885:
is a collection of computational complexity classes similar to the W hierarchy. However, while the W hierarchy is a hierarchy contained in NP, the A hierarchy more closely mimics the
2293:
1989:
498:
1757:
2572:
349:
2809:
2727:
2039:
2156:
1285:
1007:
2405:
1101:
1047:
915:
410:
2841:
2751:
2703:
2675:
2158:, or if and only if there is a computable, nondecreasing, unbounded function f such that all languages recognised by a nondeterministic polynomial-time Turing machine using
652:
1329:
821:
78:
when complexity is measured in terms of the input size only but that are computable in a time that is polynomial in the input size and exponential or worse in a parameter
2364:
2242:
2196:
1228:
288:
758:
707:
2452:
538:
1841:
1656:
1355:
233:
573:
2071:
1182:
965:
600:
2867:
1400:
847:
3267:. Special Double Issue on Parameterized Complexity with 15 survey articles, book review, and a Foreword by Guest Editors R. Downey, M. Fellows and M. Langston.
1874:
1691:
1622:
1121:
1185:
2083:
It is known that FPT is contained in W, and the inclusion is believed to be strict. However, resolving this issue would imply a solution to the
3074:
Cygan, Marek; Fomin, Fedor V.; Kowalik, Lukasz; Lokshtanov, Daniel; Marx, Daniel; Pilipczuk, Marcin; Pilipczuk, Michal; Saurabh, Saket (2015).
1127:
3121:
420:
is the size of the vertex cover. This means that vertex cover is fixed-parameter tractable with the size of the solution as the parameter.
101:, problems is considered unlikely, if input parameters are not fixed; all known solving algorithms for these problems require time that is
2459:
1506:) tape alphabet size is fixed-parameter tractable. Crucially, the branching of the Turing machine at each step is allowed to depend on
849:
would run in polynomial time in the size of the input. Thus, if graph coloring parameterised by the number of colors were in FPT, then
109:(FPT) algorithm, because the problem can be solved efficiently (i.e., in polynomial time) for constant values of the fixed parameter.
90:
is relatively small then such problems can still be considered "tractable" despite their traditional classification as "intractable".
1126:
Obviously, FPT contains all polynomial-time computable problems. Moreover, it contains all optimisation problems in NP that allow an
3302:
17:
1555:
3197:
2993:
177:
3251:
3207:
3139:
3111:
3083:
3064:
2898:
116:
is fixed are called parameterized problems. A parameterized problem that allows for such an FPT algorithm is said to be a
3129:
2581:
3166:
3297:
2298:
856:
There are a number of alternative definitions of FPT. For example, the running-time requirement can be replaced by
2756:
2615:
39:
3041:. Mathematical Foundations of Computer Science. Vol. 4162. Berlin, Heidelberg: Springer. pp. 238–249.
3264:
2482:
1562:
steps ("short multi-tape Turing machine acceptance" problem). Crucially, the branching is allowed to depend on
1474:
steps ("short Turing machine acceptance" problem). This also applies to nondeterministic Turing machines with
1461:
2259:
1931:
440:
1696:
2516:
293:
3186:
Solving NP-hard problems on graphs that are almost trees and an application to facility location problems
2790:
2708:
1994:
2870:
2101:
2510:
1245:
2369:
1376:: given a Boolean formula written as an AND of ORs of ANDs of ... of possibly negated variables, with
1052:
2886:
859:
370:
106:
2822:
2732:
2684:
2656:
3234:
3047:
1570:-complete formulation allows only single-tape Turing machines, but the alphabet size may depend on
612:
1290:
778:
3228:. Lecture Notes in Computer Science. Vol. 1683. Springer Berlin Heidelberg. pp. 14–31.
2906:
1012:
2343:
2221:
2163:
1195:
255:
3282:
3229:
3042:
2095:
926:
724:
673:
659:
51:
43:
2421:
507:
1820:
1635:
1451:
1334:
1148:
is a collection of computational complexity classes. A parameterized problem is in the class
970:
218:
543:
3260:
2902:
2044:
1155:
938:
578:
148:
2677:-hard already for a constant value of the parameter. That is, there is a "slice" of fixed
8:
2846:
1379:
850:
826:
71:
1230:
if and only if there is a satisfying assignment to the inputs that assigns 1 to exactly
3172:
1850:
1661:
1598:
1106:
3247:
3203:
3176:
3162:
3135:
3107:
3079:
3060:
2969:
50:
parameters of the input or output. The complexity of a problem is then measured as a
3213:
3239:
3193:
3154:
3052:
3002:
2961:
102:
31:
2090:
Other connections to unparameterised computational complexity are that FPT equals
1899:
Question: Does the formula have a satisfying assignment of
Hamming weight exactly
3097:
2812:
1806:
1545:
1470:
deciding if a given nondeterministic single-tape Turing machine accepts within
764:
3007:
2988:
2965:
3291:
2973:
2252:
integers, stored in binary. Since the highest any of these numbers can be is
918:
3243:
3149:
Fomin, Fedor V.; Lokshtanov, Daniel; Saurabh, Saket; Zehavi, Meirav (2019).
2949:
1794:
is the maximal number of gates on any path from the root to a leaf, and the
1693:
is the class of parameterized problems that fpt-reduce to this problem, and
93:
The existence of efficient, exact, and deterministic solving algorithms for
3221:
3125:
2340:
total bits are needed to encode a choice. Therefore we can select a subset
710:
662:
problem, parameterised by the number of variables. A given formula of size
367:
For example, there is an algorithm that solves the vertex cover problem in
75:
3158:
2084:
1406:
alternations between AND and OR), can it be satisfied by setting exactly
94:
3056:
2470:
2248:
such that a certain property holds. We can encode a choice as a list of
917:. Also, a parameterised problem is in FPT if it has a so-called kernel.
504:. Typically, this function is thought of as single exponential, such as
3093:
2210:
can be loosely thought of as the class of problems where we have a set
1498:)-dimensional tapes, but even with this extension, the restriction to
767:
parameterised by the number of colors. It is known that 3-coloring is
1510:, the size of the input. In this way, the Turing machine may explore
1184:
can be transformed (in fpt-time) to a combinatorial circuit that has
63:. The first systematic work on parameterized complexity was done by
1928:
is the class of problems that can be decided by a nondeterministic
609:(fixed parameter linear) is the class of problems solvable in time
124:, and the early name of the theory of parameterized complexity was
2418:
is the class of parameterized problems that can be solved in time
74:, there exist many natural problems that require super-polynomial
768:
98:
55:
2950:"Fixed-Parameter Tractability and Completeness I: Basic Results"
2509:
is the class of parameterized problems that can be solved by a
1566:(like the W variant), as is the number of tapes. An alternate
86:
is fixed at a small value and the growth of the function over
1413:
Many natural computational problems occupy the lower levels,
3148:
763:
An example of a problem that is thought not to be in FPT is
3073:
1805:
Question: Does the formula have a satisfying assignment of
3277:
166:
complexity theory. This concept is formalized as follows:
3183:
2889:
from classical complexity. It is known that A = W holds.
235:
is a finite alphabet. The second component is called the
208:{\displaystyle L\subseteq \Sigma ^{*}\times \mathbb {N} }
60:
3184:
Gurevich, Yuri; Stockmeyer, Larry; Vishkin, Uzi (1984).
131:
Many problems have the following form: given an object
54:
of those parameters. This allows the classification of
46:
according to their inherent difficulty with respect to
3015:
1128:
efficient polynomial-time approximation scheme (EPTAS)
2849:
2825:
2793:
2759:
2735:
2711:
2687:
2659:
2618:
2584:
2519:
2424:
2372:
2346:
2301:
2262:
2224:
2166:
2104:
2047:
1997:
1934:
1853:
1823:
1699:
1664:
1638:
1601:
1382:
1337:
1293:
1248:
1198:
1158:
1109:
1055:
1015:
973:
941:
862:
829:
781:
727:
676:
615:
581:
546:
510:
443:
437:
problems, which are those that can be solved in time
373:
296:
258:
221:
180:
162:
In this way, parameterized complexity can be seen as
3224:(1999). "Descriptive and Parameterized Complexity".
3151:
3039:
2948:Downey, Rod G.; Fellows, Michael R. (August 1995).
2605:{\displaystyle {\textsf {FPT}}={\textsf {para-NP}}}
658:. FPL is thus a subclass of FPT. An example is the
2861:
2835:
2803:
2779:
2745:
2721:
2697:
2669:
2638:
2604:
2566:
2446:
2399:
2358:
2332:
2287:
2236:
2190:
2150:
2065:
2033:
1983:
1868:
1835:
1751:
1685:
1650:
1616:
1394:
1349:
1323:
1279:
1222:
1176:
1115:
1095:
1041:
1001:
959:
909:
841:
815:
752:
701:
646:
594:
567:
532:
492:
404:
343:
282:
227:
207:
1624:can be defined using the family of Weighted Weft-
3289:
670:variables can be checked by brute force in time
2333:{\displaystyle k\cdot \lceil \log _{2}n\rceil }
2041:nondeterministic choices in the computation on
1361:hierarchy are also closed under fpt-reduction.
359:. The corresponding complexity class is called
925:FPT is closed under a parameterised notion of
760:, so the vertex cover problem is also in FPL.
3092:
3037:Chen, Jianer; Kanj, Iyad A.; Xia, Ge (2006).
2947:
64:
2780:{\displaystyle {\textsf {P}}={\textsf {NP}}}
2639:{\displaystyle {\textsf {P}}={\textsf {NP}}}
2327:
2308:
2282:
2263:
967:of some problem into an equivalent instance
3192:
3153:. Cambridge University Press. p. 528.
3036:
2925:
2295:bits are needed for each number. Therefore
355:is an arbitrary function depending only on
1888:Input: A Boolean formula of depth at most
1778:Input: A Boolean formula of depth at most
3233:
3120:
3046:
3021:
3006:
2987:Buss, Jonathan F; Islam, Tarique (2006).
2986:
2828:
2796:
2772:
2762:
2738:
2714:
2690:
2662:
2631:
2621:
2597:
2587:
2078:
201:
61:Gurevich, Stockmeyer & Vishkin (1984)
27:Branch of computational complexity theory
3199:Invitation to Fixed-Parameter Algorithms
2288:{\displaystyle \lceil \log _{2}n\rceil }
1991:-time Turing machine that makes at most
935:. Such reductions transform an instance
2905:an algorithm running in FPT time might
2871:Graph coloring#Computational complexity
2705:-hard. A parameterized problem that is
14:
3290:
3188:. Journal of the ACM. p. 459-473.
1984:{\displaystyle h(k)\cdot {|x|}^{O(1)}}
1892:with an AND-gate on top, and a number
1460:deciding if a given graph contains an
1257:
1254:
1251:
493:{\displaystyle f(k)\cdot {|x|}^{O(1)}}
3263:. Volume 51, Numbers 1 and 3 (2008).
3220:
2936:
2899:Parameterized approximation algorithm
2200:nondeterministic choices are in
1752:{\displaystyle W=\bigcup _{d\geq t}W}
1554:deciding if a given nondeterministic
1544:deciding if a given graph contains a
1450:deciding if a given graph contains a
423:
3283:Compendium of Parameterized Problems
2567:{\displaystyle f(k)\cdot |x|^{O(1)}}
2465:
2218:items, and we want to find a subset
1802:on any path from the root to a leaf.
344:{\displaystyle f(k)\cdot |x|^{O(1)}}
2804:{\displaystyle {\textsf {para-NP}}}
2722:{\displaystyle {\textsf {para-NP}}}
2034:{\displaystyle O(f(k)\cdot \log n)}
143:have some property that depends on
24:
2151:{\displaystyle \exp(o(n))m^{O(1)}}
290:?" can be decided in running time
222:
188:
25:
3314:
3271:
2729:-hard cannot belong to the class
1280:{\displaystyle {\mathsf {FPT}}=W}
120:problem and belongs to the class
112:Problems in which some parameter
3278:Wiki on parameterized complexity
2989:"Simplifying the weft hierarchy"
2469:
2400:{\displaystyle O(k\cdot \log n)}
1096:{\displaystyle f(k)\cdot p(|x|)}
3303:Computational complexity theory
3131:Parameterized Complexity Theory
2811:-hard parameterized problem is
1847:-Normalize SAT is complete for
1798:is the maximal number of gates
910:{\displaystyle f(k)+|x|^{O(1)}}
405:{\displaystyle O(kn+1.274^{k})}
40:computational complexity theory
2980:
2941:
2930:
2919:
2876:
2836:{\displaystyle {\textsf {NP}}}
2815:, parameterized by the number
2746:{\displaystyle {\textsf {XP}}}
2698:{\displaystyle {\textsf {NP}}}
2670:{\displaystyle {\textsf {NP}}}
2559:
2553:
2545:
2536:
2529:
2523:
2439:
2433:
2394:
2376:
2176:
2170:
2143:
2137:
2126:
2123:
2117:
2111:
2060:
2048:
2028:
2013:
2007:
2001:
1976:
1970:
1961:
1953:
1944:
1938:
1863:
1857:
1746:
1734:
1709:
1703:
1680:
1668:
1611:
1605:
1318:
1312:
1303:
1297:
1274:
1268:
1211:
1199:
1171:
1159:
1133:
1090:
1086:
1078:
1074:
1065:
1059:
1049:) and can be computed in time
1036:
1030:
996:
974:
954:
942:
902:
896:
888:
879:
872:
866:
808:
802:
791:
785:
747:
731:
696:
680:
640:
632:
625:
619:
562:
550:
525:
519:
485:
479:
470:
462:
453:
447:
416:is the number of vertices and
399:
377:
336:
330:
322:
313:
306:
300:
271:
259:
13:
1:
3030:
2574:for some computable function
2454:for some computable function
2077:-restricted Turing machine).
771:, and an algorithm for graph
654:for some computable function
647:{\displaystyle f(k)\cdot |x|}
500:for some computable function
159:, and not in the input size.
2994:Theoretical Computer Science
2819:of colors, which is already
2458:. These problems are called
1876:under fpt-reductions. Here,
1324:{\displaystyle W\subseteq W}
816:{\displaystyle f(k)n^{O(1)}}
126:fixed-parameter tractability
42:that focuses on classifying
7:
3202:. Oxford University Press.
2892:
1540:-complete problems include
1446:-complete problems include
1402:layers of ANDs or ORs (and
1042:{\displaystyle k'\leq g(k)}
65:Downey & Fellows (1999)
10:
3319:
2511:nondeterministic algorithm
2501:
2407:nondeterministic choices.
2359:{\displaystyle T\subset S}
2237:{\displaystyle T\subset S}
2191:{\displaystyle f(n)\log n}
1884:is the following problem:
1774:is the following problem:
1374:-Normalized Satisfiability
1223:{\displaystyle (x,k)\in L}
283:{\displaystyle (x,k)\in L}
135:and a nonnegative integer
70:Under the assumption that
3078:. Springer. p. 555.
3008:10.1016/j.tcs.2005.10.002
2966:10.1137/S0097539792228228
2954:SIAM Journal on Computing
2926:Chen, Kanj & Xia 2006
2887:polynomial-time hierarchy
2787:. A classic example of a
1817:It can be shown that for
1556:multi-tape Turing machine
1009:of another problem (with
753:{\displaystyle O(2^{k}n)}
702:{\displaystyle O(2^{k}m)}
435:fixed parameter tractable
250:fixed-parameter tractable
147:? For instance, for the
118:fixed-parameter tractable
107:fixed-parameter tractable
3298:Parameterized complexity
3103:Parameterized Complexity
3076:Parameterized Algorithms
2913:
2447:{\displaystyle n^{f(k)}}
1800:of fan-in at least three
533:{\displaystyle 2^{O(k)}}
244:A parameterized problem
36:parameterized complexity
18:Parameterised complexity
3244:10.1007/3-540-48168-0_3
3022:Flum & Grohe (2006)
2098:can be decided in time
2079:Flum & Grohe (2006)
1836:{\displaystyle t\geq 2}
1651:{\displaystyle d\geq t}
1364:A complete problem for
1350:{\displaystyle i\leq j}
1002:{\displaystyle (x',k')}
228:{\displaystyle \Sigma }
3226:Computer Science Logic
2863:
2837:
2805:
2781:
2747:
2723:
2699:
2671:
2640:
2606:
2568:
2448:
2401:
2360:
2334:
2289:
2238:
2192:
2152:
2096:circuit satisfiability
2067:
2035:
1985:
1870:
1837:
1753:
1687:
1652:
1618:
1396:
1357:. The classes in the
1351:
1325:
1281:
1224:
1178:
1117:
1097:
1043:
1003:
961:
911:
843:
817:
754:
703:
660:Boolean satisfiability
648:
596:
569:
568:{\displaystyle f(n,k)}
534:
494:
428:
406:
345:
284:
229:
209:
44:computational problems
3159:10.1017/9781107415157
2903:optimization problems
2864:
2838:
2806:
2782:
2748:
2724:
2700:
2672:
2641:
2607:
2569:
2449:
2410:
2402:
2361:
2335:
2290:
2239:
2193:
2153:
2068:
2066:{\displaystyle (x,k)}
2036:
1986:
1871:
1843:the problem Weighted
1838:
1754:
1688:
1653:
1619:
1397:
1352:
1326:
1282:
1225:
1179:
1177:{\displaystyle (x,k)}
1118:
1098:
1044:
1004:
962:
960:{\displaystyle (x,k)}
912:
844:
818:
755:
721:can be found in time
704:
649:
597:
595:{\displaystyle k^{n}}
570:
535:
495:
407:
346:
285:
230:
210:
172:parameterized problem
3265:The Computer Journal
3261:The Computer Journal
2847:
2823:
2791:
2757:
2733:
2709:
2685:
2657:
2616:
2582:
2517:
2422:
2370:
2344:
2299:
2260:
2222:
2164:
2102:
2045:
1995:
1932:
1907:
1851:
1821:
1697:
1662:
1636:
1599:
1578:
1518:
1424:
1380:
1335:
1291:
1246:
1196:
1156:
1152:, if every instance
1107:
1053:
1013:
971:
939:
860:
827:
779:
725:
717:in a graph of order
674:
613:
579:
544:
508:
441:
371:
294:
256:
219:
178:
149:vertex cover problem
3098:Fellows, Michael R.
3057:10.1007/11821069_21
2862:{\displaystyle k=3}
2578:. It is known that
1395:{\displaystyle i+1}
842:{\displaystyle k=3}
2859:
2833:
2801:
2777:
2743:
2719:
2695:
2667:
2636:
2602:
2564:
2481:. You can help by
2444:
2397:
2356:
2330:
2285:
2234:
2188:
2148:
2063:
2031:
1981:
1866:
1833:
1749:
1730:
1683:
1648:
1614:
1514:computation paths.
1392:
1347:
1321:
1277:
1220:
1174:
1113:
1093:
1039:
999:
957:
907:
839:
813:
775:-coloring in time
750:
699:
644:
592:
565:
530:
490:
424:Complexity classes
402:
341:
280:
225:
205:
3253:978-3-540-66536-6
3209:978-0-19-856607-6
3194:Niedermeier, Rolf
3141:978-3-540-29952-3
3113:978-0-387-94883-6
3085:978-3-319-21274-6
3066:978-3-540-37791-7
2830:
2798:
2774:
2764:
2740:
2716:
2692:
2664:
2633:
2623:
2599:
2589:
2499:
2498:
2463:diagonalization.
1869:{\displaystyle W}
1782:and weft at most
1715:
1686:{\displaystyle W}
1632:SAT problems for
1617:{\displaystyle W}
1482:) tapes and even
1123:is a polynomial.
1116:{\displaystyle p}
433:FPT contains the
252:if the question "
16:(Redirected from
3310:
3257:
3237:
3217:
3212:. Archived from
3189:
3180:
3145:
3117:
3089:
3070:
3050:
3025:
3019:
3013:
3012:
3010:
2984:
2978:
2977:
2945:
2939:
2934:
2928:
2923:
2868:
2866:
2865:
2860:
2842:
2840:
2839:
2834:
2832:
2831:
2818:
2810:
2808:
2807:
2802:
2800:
2799:
2786:
2784:
2783:
2778:
2776:
2775:
2766:
2765:
2752:
2750:
2749:
2744:
2742:
2741:
2728:
2726:
2725:
2720:
2718:
2717:
2704:
2702:
2701:
2696:
2694:
2693:
2680:
2676:
2674:
2673:
2668:
2666:
2665:
2645:
2643:
2642:
2637:
2635:
2634:
2625:
2624:
2611:
2609:
2608:
2603:
2601:
2600:
2591:
2590:
2577:
2573:
2571:
2570:
2565:
2563:
2562:
2548:
2539:
2494:
2491:
2473:
2466:
2457:
2453:
2451:
2450:
2445:
2443:
2442:
2406:
2404:
2403:
2398:
2365:
2363:
2362:
2357:
2339:
2337:
2336:
2331:
2320:
2319:
2294:
2292:
2291:
2286:
2275:
2274:
2255:
2251:
2247:
2243:
2241:
2240:
2235:
2217:
2213:
2199:
2197:
2195:
2194:
2189:
2157:
2155:
2154:
2149:
2147:
2146:
2072:
2070:
2069:
2064:
2040:
2038:
2037:
2032:
1990:
1988:
1987:
1982:
1980:
1979:
1965:
1964:
1956:
1922:
1921:
1917:
1902:
1895:
1891:
1881:
1875:
1873:
1872:
1867:
1846:
1842:
1840:
1839:
1834:
1812:
1789:
1785:
1781:
1771:
1767:
1758:
1756:
1755:
1750:
1729:
1692:
1690:
1689:
1684:
1657:
1655:
1654:
1649:
1631:
1627:
1623:
1621:
1620:
1615:
1593:
1592:
1588:
1533:
1532:
1528:
1439:
1438:
1434:
1410:variables to 1?
1401:
1399:
1398:
1393:
1356:
1354:
1353:
1348:
1330:
1328:
1327:
1322:
1286:
1284:
1283:
1278:
1261:
1260:
1229:
1227:
1226:
1221:
1183:
1181:
1180:
1175:
1122:
1120:
1119:
1114:
1102:
1100:
1099:
1094:
1089:
1081:
1048:
1046:
1045:
1040:
1023:
1008:
1006:
1005:
1000:
995:
984:
966:
964:
963:
958:
916:
914:
913:
908:
906:
905:
891:
882:
851:P = NP
848:
846:
845:
840:
822:
820:
819:
814:
812:
811:
774:
759:
757:
756:
751:
743:
742:
720:
716:
708:
706:
705:
700:
692:
691:
669:
665:
657:
653:
651:
650:
645:
643:
635:
601:
599:
598:
593:
591:
590:
574:
572:
571:
566:
539:
537:
536:
531:
529:
528:
503:
499:
497:
496:
491:
489:
488:
474:
473:
465:
419:
415:
411:
409:
408:
403:
398:
397:
358:
354:
350:
348:
347:
342:
340:
339:
325:
316:
289:
287:
286:
281:
247:
234:
232:
231:
226:
214:
212:
211:
206:
204:
196:
195:
158:
146:
142:
138:
134:
123:
115:
89:
85:
81:
72:P ≠ NP
32:computer science
21:
3318:
3317:
3313:
3312:
3311:
3309:
3308:
3307:
3288:
3287:
3274:
3254:
3210:
3169:
3142:
3114:
3086:
3067:
3033:
3028:
3020:
3016:
2985:
2981:
2946:
2942:
2935:
2931:
2924:
2920:
2916:
2895:
2879:
2848:
2845:
2844:
2827:
2826:
2824:
2821:
2820:
2816:
2795:
2794:
2792:
2789:
2788:
2771:
2770:
2761:
2760:
2758:
2755:
2754:
2737:
2736:
2734:
2731:
2730:
2713:
2712:
2710:
2707:
2706:
2689:
2688:
2686:
2683:
2682:
2678:
2661:
2660:
2658:
2655:
2654:
2630:
2629:
2620:
2619:
2617:
2614:
2613:
2612:if and only if
2596:
2595:
2586:
2585:
2583:
2580:
2579:
2575:
2549:
2544:
2543:
2535:
2518:
2515:
2514:
2504:
2495:
2489:
2486:
2479:needs expansion
2455:
2429:
2425:
2423:
2420:
2419:
2413:
2371:
2368:
2367:
2345:
2342:
2341:
2315:
2311:
2300:
2297:
2296:
2270:
2266:
2261:
2258:
2257:
2253:
2249:
2245:
2223:
2220:
2219:
2215:
2211:
2165:
2162:
2161:
2159:
2133:
2129:
2103:
2100:
2099:
2094:if and only if
2046:
2043:
2042:
1996:
1993:
1992:
1966:
1960:
1952:
1951:
1950:
1933:
1930:
1929:
1923:
1919:
1915:
1913:
1912:
1900:
1893:
1889:
1879:
1852:
1849:
1848:
1844:
1822:
1819:
1818:
1810:
1787:
1786:, and a number
1783:
1779:
1769:
1765:
1719:
1698:
1695:
1694:
1663:
1660:
1659:
1637:
1634:
1633:
1629:
1625:
1600:
1597:
1596:
1594:
1590:
1586:
1584:
1583:
1558:accepts within
1534:
1530:
1526:
1524:
1523:
1462:independent set
1440:
1436:
1432:
1430:
1429:
1381:
1378:
1377:
1336:
1333:
1332:
1292:
1289:
1288:
1250:
1249:
1247:
1244:
1243:
1197:
1194:
1193:
1157:
1154:
1153:
1139:
1108:
1105:
1104:
1085:
1077:
1054:
1051:
1050:
1016:
1014:
1011:
1010:
988:
977:
972:
969:
968:
940:
937:
936:
892:
887:
886:
878:
861:
858:
857:
828:
825:
824:
798:
794:
780:
777:
776:
772:
738:
734:
726:
723:
722:
718:
714:
687:
683:
675:
672:
671:
667:
663:
655:
639:
631:
614:
611:
610:
586:
582:
580:
577:
576:
545:
542:
541:
515:
511:
509:
506:
505:
501:
475:
469:
461:
460:
459:
442:
439:
438:
431:
426:
417:
413:
393:
389:
372:
369:
368:
356:
352:
326:
321:
320:
312:
295:
292:
291:
257:
254:
253:
245:
239:of the problem.
220:
217:
216:
200:
191:
187:
179:
176:
175:
164:two-dimensional
156:
144:
140:
136:
132:
121:
113:
97:, or otherwise
87:
83:
79:
38:is a branch of
28:
23:
22:
15:
12:
11:
5:
3316:
3306:
3305:
3300:
3286:
3285:
3280:
3273:
3272:External links
3270:
3269:
3268:
3258:
3252:
3235:10.1.1.25.9250
3218:
3216:on 2008-09-24.
3208:
3190:
3181:
3168:978-1107057760
3167:
3146:
3140:
3118:
3112:
3094:Downey, Rod G.
3090:
3084:
3071:
3065:
3048:10.1.1.432.831
3032:
3029:
3027:
3026:
3014:
3001:(3): 303–313.
2979:
2960:(4): 873–921.
2940:
2929:
2917:
2915:
2912:
2911:
2910:
2894:
2891:
2878:
2875:
2858:
2855:
2852:
2813:graph coloring
2769:
2628:
2594:
2561:
2558:
2555:
2552:
2547:
2542:
2538:
2534:
2531:
2528:
2525:
2522:
2503:
2500:
2497:
2496:
2476:
2474:
2441:
2438:
2435:
2432:
2428:
2412:
2409:
2396:
2393:
2390:
2387:
2384:
2381:
2378:
2375:
2355:
2352:
2349:
2329:
2326:
2323:
2318:
2314:
2310:
2307:
2304:
2284:
2281:
2278:
2273:
2269:
2265:
2233:
2230:
2227:
2187:
2184:
2181:
2178:
2175:
2172:
2169:
2145:
2142:
2139:
2136:
2132:
2128:
2125:
2122:
2119:
2116:
2113:
2110:
2107:
2062:
2059:
2056:
2053:
2050:
2030:
2027:
2024:
2021:
2018:
2015:
2012:
2009:
2006:
2003:
2000:
1978:
1975:
1972:
1969:
1963:
1959:
1955:
1949:
1946:
1943:
1940:
1937:
1911:
1906:
1905:
1904:
1897:
1882:-Normalize SAT
1865:
1862:
1859:
1856:
1832:
1829:
1826:
1815:
1814:
1807:Hamming weight
1803:
1764:Weighted Weft-
1748:
1745:
1742:
1739:
1736:
1733:
1728:
1725:
1722:
1718:
1714:
1711:
1708:
1705:
1702:
1682:
1679:
1676:
1673:
1670:
1667:
1647:
1644:
1641:
1613:
1610:
1607:
1604:
1582:
1577:
1576:
1575:
1552:
1546:dominating set
1522:
1517:
1516:
1515:
1468:
1458:
1428:
1423:
1391:
1388:
1385:
1346:
1343:
1340:
1320:
1317:
1314:
1311:
1308:
1305:
1302:
1299:
1296:
1276:
1273:
1270:
1267:
1264:
1259:
1256:
1253:
1219:
1216:
1213:
1210:
1207:
1204:
1201:
1173:
1170:
1167:
1164:
1161:
1138:
1132:
1112:
1092:
1088:
1084:
1080:
1076:
1073:
1070:
1067:
1064:
1061:
1058:
1038:
1035:
1032:
1029:
1026:
1022:
1019:
998:
994:
991:
987:
983:
980:
976:
956:
953:
950:
947:
944:
932:fpt-reductions
904:
901:
898:
895:
890:
885:
881:
877:
874:
871:
868:
865:
838:
835:
832:
810:
807:
804:
801:
797:
793:
790:
787:
784:
765:graph coloring
749:
746:
741:
737:
733:
730:
698:
695:
690:
686:
682:
679:
642:
638:
634:
630:
627:
624:
621:
618:
589:
585:
564:
561:
558:
555:
552:
549:
527:
524:
521:
518:
514:
487:
484:
481:
478:
472:
468:
464:
458:
455:
452:
449:
446:
430:
427:
425:
422:
401:
396:
392:
388:
385:
382:
379:
376:
365:
364:
338:
335:
332:
329:
324:
319:
315:
311:
308:
305:
302:
299:
279:
276:
273:
270:
267:
264:
261:
241:
240:
224:
203:
199:
194:
190:
186:
183:
174:is a language
26:
9:
6:
4:
3:
2:
3315:
3304:
3301:
3299:
3296:
3295:
3293:
3284:
3281:
3279:
3276:
3275:
3266:
3262:
3259:
3255:
3249:
3245:
3241:
3236:
3231:
3227:
3223:
3222:Grohe, Martin
3219:
3215:
3211:
3205:
3201:
3200:
3195:
3191:
3187:
3182:
3178:
3174:
3170:
3164:
3160:
3156:
3152:
3147:
3143:
3137:
3133:
3132:
3127:
3126:Grohe, Martin
3123:
3119:
3115:
3109:
3105:
3104:
3099:
3095:
3091:
3087:
3081:
3077:
3072:
3068:
3062:
3058:
3054:
3049:
3044:
3040:
3035:
3034:
3024:, p. 39.
3023:
3018:
3009:
3004:
3000:
2996:
2995:
2990:
2983:
2975:
2971:
2967:
2963:
2959:
2955:
2951:
2944:
2938:
2933:
2927:
2922:
2918:
2909:the solution.
2908:
2904:
2900:
2897:
2896:
2890:
2888:
2884:
2874:
2872:
2856:
2853:
2850:
2814:
2767:
2652:
2649:A problem is
2647:
2626:
2592:
2556:
2550:
2540:
2532:
2526:
2520:
2512:
2508:
2493:
2484:
2480:
2477:This section
2475:
2472:
2468:
2467:
2464:
2461:
2436:
2430:
2426:
2417:
2408:
2391:
2388:
2385:
2382:
2379:
2373:
2353:
2350:
2347:
2324:
2321:
2316:
2312:
2305:
2302:
2279:
2276:
2271:
2267:
2231:
2228:
2225:
2209:
2205:
2203:
2185:
2182:
2179:
2173:
2167:
2140:
2134:
2130:
2120:
2114:
2108:
2105:
2097:
2093:
2088:
2086:
2081:
2080:
2076:
2057:
2054:
2051:
2025:
2022:
2019:
2016:
2010:
2004:
1998:
1973:
1967:
1957:
1947:
1941:
1935:
1927:
1918:
1910:
1898:
1887:
1886:
1885:
1883:
1860:
1854:
1830:
1827:
1824:
1808:
1804:
1801:
1797:
1793:
1777:
1776:
1775:
1773:
1760:
1743:
1740:
1737:
1731:
1726:
1723:
1720:
1716:
1712:
1706:
1700:
1677:
1674:
1671:
1665:
1645:
1642:
1639:
1608:
1602:
1589:
1581:
1573:
1569:
1565:
1561:
1557:
1553:
1551:
1547:
1543:
1542:
1541:
1539:
1529:
1521:
1513:
1509:
1505:
1501:
1497:
1493:
1489:
1485:
1481:
1477:
1473:
1469:
1467:
1463:
1459:
1457:
1453:
1449:
1448:
1447:
1445:
1435:
1427:
1422:
1420:
1416:
1411:
1409:
1405:
1389:
1386:
1383:
1375:
1373:
1367:
1362:
1360:
1344:
1341:
1338:
1315:
1309:
1306:
1300:
1294:
1271:
1265:
1262:
1240:
1237:
1233:
1217:
1214:
1208:
1205:
1202:
1191:
1187:
1168:
1165:
1162:
1151:
1147:
1145:
1136:
1131:
1129:
1124:
1110:
1082:
1071:
1068:
1062:
1056:
1033:
1027:
1024:
1020:
1017:
992:
989:
985:
981:
978:
951:
948:
945:
934:
933:
928:
923:
920:
919:Kernelization
899:
893:
883:
875:
869:
863:
854:
852:
836:
833:
830:
805:
799:
795:
788:
782:
770:
766:
761:
744:
739:
735:
728:
712:
693:
688:
684:
677:
661:
636:
628:
622:
616:
608:
603:
587:
583:
559:
556:
553:
547:
522:
516:
512:
482:
476:
466:
456:
450:
444:
436:
421:
394:
390:
386:
383:
380:
374:
362:
333:
327:
317:
309:
303:
297:
277:
274:
268:
265:
262:
251:
243:
242:
238:
197:
192:
184:
181:
173:
169:
168:
167:
165:
160:
154:
150:
129:
127:
119:
110:
108:
104:
100:
96:
91:
77:
73:
68:
66:
62:
57:
53:
49:
45:
41:
37:
33:
19:
3225:
3214:the original
3198:
3185:
3150:
3134:. Springer.
3130:
3106:. Springer.
3102:
3075:
3038:
3017:
2998:
2992:
2982:
2957:
2953:
2943:
2937:Grohe (1999)
2932:
2921:
2882:
2880:
2651:para-NP-hard
2650:
2648:
2506:
2505:
2487:
2483:adding to it
2478:
2415:
2414:
2207:
2206:
2201:
2091:
2089:
2082:
2074:
1925:
1924:
1908:
1877:
1816:
1799:
1795:
1791:
1763:
1761:
1595:
1579:
1571:
1567:
1563:
1559:
1549:
1537:
1536:Examples of
1535:
1519:
1511:
1507:
1503:
1499:
1495:
1491:
1487:
1483:
1479:
1475:
1471:
1465:
1455:
1443:
1442:Examples of
1441:
1425:
1418:
1414:
1412:
1407:
1403:
1371:
1369:
1365:
1363:
1358:
1241:
1235:
1234:inputs. The
1231:
1192:, such that
1189:
1149:
1143:
1142:
1140:
1134:
1125:
931:
930:
924:
855:
762:
711:vertex cover
606:
604:
434:
432:
412:time, where
366:
360:
249:
236:
171:
163:
161:
152:
130:
125:
117:
111:
92:
82:. Hence, if
76:running time
69:
47:
35:
29:
2907:approximate
2883:A hierarchy
2877:A hierarchy
2085:P versus NP
103:exponential
95:NP-complete
3292:Categories
3122:Flum, Jörg
3031:References
2843:-hard for
2490:April 2019
1242:Note that
927:reductions
605:The class
575:, such as
3230:CiteSeerX
3177:263888582
3043:CiteSeerX
2974:0097-5397
2753:, unless
2653:if it is
2533:⋅
2460:slicewise
2389:
2383:⋅
2351:⊂
2328:⌉
2322:
2309:⌈
2306:⋅
2283:⌉
2277:
2264:⌈
2229:⊂
2183:
2109:
2087:problem.
2023:
2017:⋅
1948:⋅
1878:Weighted
1828:≥
1724:≥
1717:⋃
1643:≥
1370:Weighted
1342:≤
1307:⊆
1215:∈
1146:hierarchy
1137:hierarchy
1069:⋅
1025:≤
629:⋅
457:⋅
310:⋅
275:∈
237:parameter
223:Σ
198:×
193:∗
189:Σ
185:⊆
3196:(2006).
3128:(2006).
3100:(1999).
2893:See also
2681:that is
2513:in time
2244:of size
1809:exactly
1548:of size
1464:of size
1454:of size
1331:for all
1188:at most
1021:′
993:′
982:′
713:of size
351:, where
215:, where
52:function
48:multiple
2797:para-NP
2715:para-NP
2598:para-NP
2507:para-NP
2502:para-NP
2198:
2160:
1768:-Depth-
1628:-Depth-
929:called
769:NP-hard
139:, does
99:NP-hard
56:NP-hard
3250:
3232:
3206:
3175:
3165:
3138:
3110:
3082:
3063:
3045:
2972:
2901:, for
1914:": -->
1790:. The
1762:Here,
1585:": -->
1525:": -->
1452:clique
1431:": -->
1103:where
3173:S2CID
2914:Notes
2869:(see
2366:with
1792:depth
1490:) of
666:with
391:1.274
3248:ISBN
3204:ISBN
3163:ISBN
3136:ISBN
3108:ISBN
3080:ISBN
3061:ISBN
2970:ISSN
2881:The
1916:edit
1796:weft
1587:edit
1527:edit
1433:edit
1417:and
1287:and
1236:weft
1186:weft
1141:The
823:for
709:. A
602:.
153:only
3240:doi
3155:doi
3053:doi
3003:doi
2999:351
2962:doi
2873:).
2588:FPT
2485:.
2386:log
2313:log
2268:log
2214:of
2180:log
2106:exp
2073:(a
2020:log
1772:SAT
1368:is
607:FPL
429:FPT
361:FPT
248:is
155:in
122:FPT
30:In
3294::
3246:.
3238:.
3171:.
3161:.
3124:;
3096:;
3059:.
3051:.
2997:.
2991:.
2968:.
2958:24
2956:.
2952:.
2829:NP
2773:NP
2739:XP
2691:NP
2663:NP
2646:.
2632:NP
2416:XP
2411:XP
2256:,
2204:.
1759:.
1658::
1421:.
1130:.
853:.
170:A
128:.
67:.
34:,
3256:.
3242::
3179:.
3157::
3144:.
3116:.
3088:.
3069:.
3055::
3011:.
3005::
2976:.
2964::
2857:3
2854:=
2851:k
2817:k
2768:=
2763:P
2679:k
2627:=
2622:P
2593:=
2576:f
2560:)
2557:1
2554:(
2551:O
2546:|
2541:x
2537:|
2530:)
2527:k
2524:(
2521:f
2492:)
2488:(
2456:f
2440:)
2437:k
2434:(
2431:f
2427:n
2395:)
2392:n
2380:k
2377:(
2374:O
2354:S
2348:T
2325:n
2317:2
2303:k
2280:n
2272:2
2254:n
2250:k
2246:k
2232:S
2226:T
2216:n
2212:S
2208:W
2202:P
2186:n
2177:)
2174:n
2171:(
2168:f
2144:)
2141:1
2138:(
2135:O
2131:m
2127:)
2124:)
2121:n
2118:(
2115:o
2112:(
2092:W
2075:k
2061:)
2058:k
2055:,
2052:x
2049:(
2029:)
2026:n
2014:)
2011:k
2008:(
2005:f
2002:(
1999:O
1977:)
1974:1
1971:(
1968:O
1962:|
1958:x
1954:|
1945:)
1942:k
1939:(
1936:h
1926:W
1920:]
1909:W
1903:?
1901:k
1896:.
1894:k
1890:t
1880:t
1864:]
1861:t
1858:[
1855:W
1845:t
1831:2
1825:t
1813:?
1811:k
1788:k
1784:t
1780:d
1770:d
1766:t
1747:]
1744:d
1741:,
1738:t
1735:[
1732:W
1727:t
1721:d
1713:=
1710:]
1707:t
1704:[
1701:W
1681:]
1678:d
1675:,
1672:t
1669:[
1666:W
1646:t
1640:d
1630:d
1626:t
1612:]
1609:t
1606:[
1603:W
1591:]
1580:W
1574:.
1572:n
1568:W
1564:n
1560:k
1550:k
1538:W
1531:]
1520:W
1512:n
1508:n
1504:k
1502:(
1500:f
1496:k
1494:(
1492:f
1488:k
1486:(
1484:f
1480:k
1478:(
1476:f
1472:k
1466:k
1456:k
1444:W
1437:]
1426:W
1419:W
1415:W
1408:k
1404:i
1390:1
1387:+
1384:i
1372:i
1366:W
1359:W
1345:j
1339:i
1319:]
1316:j
1313:[
1310:W
1304:]
1301:i
1298:[
1295:W
1275:]
1272:0
1269:[
1266:W
1263:=
1258:T
1255:P
1252:F
1232:k
1218:L
1212:)
1209:k
1206:,
1203:x
1200:(
1190:i
1172:)
1169:k
1166:,
1163:x
1160:(
1150:W
1144:W
1135:W
1111:p
1091:)
1087:|
1083:x
1079:|
1075:(
1072:p
1066:)
1063:k
1060:(
1057:f
1037:)
1034:k
1031:(
1028:g
1018:k
997:)
990:k
986:,
979:x
975:(
955:)
952:k
949:,
946:x
943:(
903:)
900:1
897:(
894:O
889:|
884:x
880:|
876:+
873:)
870:k
867:(
864:f
837:3
834:=
831:k
809:)
806:1
803:(
800:O
796:n
792:)
789:k
786:(
783:f
773:k
748:)
745:n
740:k
736:2
732:(
729:O
719:n
715:k
697:)
694:m
689:k
685:2
681:(
678:O
668:k
664:m
656:f
641:|
637:x
633:|
626:)
623:k
620:(
617:f
588:n
584:k
563:)
560:k
557:,
554:n
551:(
548:f
526:)
523:k
520:(
517:O
513:2
502:f
486:)
483:1
480:(
477:O
471:|
467:x
463:|
454:)
451:k
448:(
445:f
418:k
414:n
400:)
395:k
387:+
384:n
381:k
378:(
375:O
363:.
357:k
353:f
337:)
334:1
331:(
328:O
323:|
318:x
314:|
307:)
304:k
301:(
298:f
278:L
272:)
269:k
266:,
263:x
260:(
246:L
202:N
182:L
157:k
145:k
141:x
137:k
133:x
114:k
88:k
84:k
80:k
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.