ABSTRACT

The theory of parameterized computational complexity, pioneered by Downey andFellows, is motivated by the observation that many NP-complete problems have as input several parameters, some of which are likely to be small in practice. While the classical notion of feasible computation is associated with an algorithm whose running time is a polynomial in the input size, parameterized complexity strengthens it by allowing exponential running time in the (small) parameters associated with the input.