https://www.dagstuhl.de/01311

July 29 – August 3 , 2001, Dagstuhl Seminar 01311

Parameterized Complexity

Organizers

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)

For support, please contact

Dagstuhl Service Team

Documents

List of Participants
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

Documentation

In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.

 

Download overview leaflet (PDF).

Publications

Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.