Fixed Parameter Tractability and Completeness.

Abstract

For many fixed-parameter problems that are trivially solvable in polynomial-time, such as k-Dominating Set, essentially no better algorithm is presently known than the one which tries all possible solutions. Other problems, such as k-Feedback Vertex Set, exhibit fixed-parameter tractability: for each fixed k the problem is solvable in time bounded by a polynomial of degree c, where c is a constant independent of k. We show that for this problem, and for the problem of determining whether a graph has k disjoint cycles, we may take c = 1. We also show that if Dominating Set is fixed-parameter tractable, then so are a variety of parameterized problems, such as Independent Set. Some of the main results of a completeness theory for fixed-parameter intractability are surveyed. 1.