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