View article

For many fixed-parameter problems that are trivially soluable in polynomial time, such as DOMINATING SET, essentially no better algorithm is presently known than the one which tries all possible solutions. Other problems, such as FEEDBACK VERTEX SET, exhibit fixed-parameter tractability: for each fixed k the problem is soluable in time bounded by a polynomial of degree c, where c is a constant independent of k. We establish the main results of a completeness program which addresses the apparent fixed-parameter intractability of many parameterized problems. In particular, we define a hierarchy of classes of parameterized problems $FPT \subseteq W[1] \subseteq W[2] \subseteq \cdots \subseteq W[SAT] \subseteq W [P]$ and identify natural complete problems for for . (In other papers we have shown many problems complete for .) DOMINATING SET is shown to be complete for  …