Logic and interactions 2012

Parameterized Complexity is a new theoretical framework for the analysis and solution of hard computational problems. Virtually in every conceivable context we know more about the problem input than just its size in bytes. The key idea of parameterized complexity is to represent this additional information in terms of a parameter, and to study computational problems in a two-dimensional setting formed by the input size and the parameter. This setting gives rise to a new theory of algorithms and complexity that allows a more fine-grained complexity analysis than the classical one-dimensional setting. Central to the theory is the notion of fixed-parameter tractability, which relaxes the classical notion of tractability by admitting algorithms whose runtime is exponential, but only in terms of the parameter of the problem instance. In recent years, ideas from parameterized complexity theory have found their way into various areas of computer science, such as artificial intelligence, database theory, computational logic, computational social choice, computational geometry, and computational biology.

In the first part of this tutorial we will discuss algorithmic methods for establishing fixed-parameter tractability, including the method of bounded search trees, reductions to a problem kernel, and algorithmic meta theorems. In the second part we will discuss the main concepts of parameterized intractability, which are similar to the theory of NP-completeness, and allow to provide strong evidence that a parameterized problem is not fixed-parameter tractable.