Parameterized Complexity

Motivation

Parameterized complexity is a new and promising approach to the central issue of how to cope with problems that are NP-hard or worse -- as is so frequently the case in the natural world of computing. The key idea is to isolate some aspect(s) or part(s) of the input as the parameter , and to confine the seemingly inevitable combinatorial explosion of computational difficulty to an additive function of the parameter, with other costs being polynomial (called FPT complexity). An example is the NP-complete VERTEX COVER ("conflict resolution") problem that is now known to be solvable in less than 1.29^k +kn steps for conflict graphs of size n . This algorithm works well for k <= 200 and has several applications in computational biology.

Many important "heuristic" algorithms currently in use are FPT algorithms, previously unrecognized as such. Type-checking in ML provides another example. Although complete for EXPTIME in general, it is solved in practice in time 2^k + n for programs of size n , where the k is the nesting depth of declarations. Although many naturally parameterized problems are in FPT, some are not. The rich positive toolkit of novel techniques for designing and improving FPT algorithms is accompanied in the theory by a corresponding negative toolkit that supports a rich structure theory of parametric intractability. But the real excitement is in the rapidly developing systematic connections between FPT and useful heuristic algorithms -- a new and exciting bridge between the theory of computing and computing in practice.

The organizers of the seminar strongly believe that knowledge of parameterized complexity techniques and results belongs into the toolkit of every algorithm designer. The purpose of the seminar is to bring together leading experts from all over the world, and from the diverse areas of computer science that have been attracted to this new framework. The seminar is intended as the first larger international meeting with a specific focus on parameterized complexity, and it will serve as a driving force in the development of the field.