Fixed-parameter intractability
Rodney G. Downey, Michael R. Fellows · 2003
The authors consider the complexity behavior of parametrized problems that they term fixed-parameter tractability: for each fixed parameter value y the problem is solvable in time O(n/sup c/), where c is a constant independent of the parameter y. They introduce a structure theory with which to address the apparent intractability of some parameterized problems, and they obtain completeness, density, and separation/collapse results. The greatest appeal of the theory is in the wide range of natural problems to which it can be applied, and in the practical significance of fixed-parameter problem complexities. Technical aspects are also interesting.>