29. Juli – 03. August 2001, Dagstuhl-Seminar 01311

Parameterized Complexity


Rodney Downey (Victoria University of Wellington, NZ)
Michael R. Fellows (University of Newcastle, AU)
Rolf Niedermeier (Universität Jena, DE)
Peter Rossmanith (RWTH Aachen, DE)

Auskunft zu diesem Dagstuhl-Seminar erteilt

Dagstuhl Service Team


Dagstuhl-Seminar-Report 316


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.29k +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 2k + 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.

Related Dagstuhl-Seminar


In der Reihe Dagstuhl Reports werden alle Dagstuhl-Seminare und Dagstuhl-Perspektiven-Workshops dokumentiert. Die Organisatoren stellen zusammen mit dem Collector des Seminars einen Bericht zusammen, der die Beiträge der Autoren zusammenfasst und um eine Zusammenfassung ergänzt.


Download Übersichtsflyer (PDF).

Dagstuhl's Impact

Bitte informieren Sie uns, wenn eine Veröffentlichung ausgehend von Ihrem Seminar entsteht. Derartige Veröffentlichungen werden von uns in der Rubrik Dagstuhl's Impact separat aufgelistet  und im Erdgeschoss der Bibliothek präsentiert.


Es besteht weiterhin die Möglichkeit, eine umfassende Kollektion begutachteter Arbeiten in der Reihe Dagstuhl Follow-Ups zu publizieren.