Parameterized Complexity

pioneered by Downey and Fellows, is motivated by the
observation that many NP-complete problems take as input
two objects, for example, perhaps a graph G and an integer k.
In some cases, e.g., VERTEX COVER, the problem can be solved
in linear time for every fixed parameter value whereas for problems
like CLIQUE AND DOMINATING SET, we have the contrasting situation
where the best known algorithms are based on brute force
essentially, requiring time Omega (n^k). The theory of parameterized
complexity explores this apparent qualitative difference between these
problems (for fixed parameter values). It is particularly relevant
and useful to problems where a small range of parameter
values cover important applications as in computational biology
and VLSI. The theory can also be considered as giving a new approach to
deal with hard problems.

In these lectures, I will first introduce the notion of
fixed parameter tractability. Then we will survey some
techniques that have emerged over time to show a parameterized
problem fixed parameter tractable.
Some of these techniques are easy but powerful while others are
based on advanced techniques like hashing, treewidth machinery and the recent
powerful graph minor theorems of Robertson and Seymour.

Then we will look at parameterized reductions and the completeness
theory developed by Downey and Fellows to identify apparent fixed
parameter intractable problems.

Some of the problems I will be using for illustration include
the parameterized versions of VERTEX COVER, FEEDBACK VERTEX SET,
MAXCUT, MAXSAT and DOMINATING SET, LONGEST PATH and LONGEST CYCLE.

Some references:

1. Parameterized Complexity, R. G. Downey and M. R. Fellows,
Springer 1998 (not sure it has appeared yet)

2. Fixed Parameter Intractability, R. G. Downey and M. R. Fellows,
STRUCTURES (1992) 36-49.

3. Fixed Parameter Tractability and Completeness I: Basic Theory,
R. G. Downey and M. R. Fellows, SICOMP 24 (1995) 873-921.

4. Fixed Parameter Tractability and Completeness II: Completeness for W[1],
R. G. Downey and M. R. Fellows, TCS 141 (1995) 109-131.