Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Within this website:
External resources:
Within this website:
External resources:
  • the dblp Computer Science Bibliography

Dagstuhl Seminar 01311

Parameterized Complexity

( Jul 29 – Aug 03, 2001 )

Please use the following short url to reference this page:



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.

  • Faisal N. Abu-Khzam (Lebanese American University, LB) [dblp]
  • Jochen Alber (Universität Tübingen, DE)
  • Witold Charatonik (MPI für Informatik - Saarbrücken, DE)
  • Jianer Chen (Texas A&M University - College Station, US) [dblp]
  • Benny Chor (Tel Aviv University, IL)
  • Frederic Dorn (Universität Tübingen, DE) [dblp]
  • Rodney Downey (Victoria University of Wellington, NZ) [dblp]
  • Thomas Erlebach (University of Leicester, GB) [dblp]
  • Patricia Evans (University of New Brunswick at Fredericton, CA)
  • Michael R. Fellows (University of Newcastle, AU) [dblp]
  • Henning Fernau (University of Hertfordshire, GB) [dblp]
  • Jiri Fiala (Charles University - Prague, CZ)
  • Jörg Flum (Universität Freiburg, DE) [dblp]
  • Bernd Gärtner (Perspectix AG Zürich, CH) [dblp]
  • Andreas Goerdt (TU Chemnitz, DE) [dblp]
  • Judy Goldsmith (University of Kentucky - Lexington, US) [dblp]
  • Jens Gramm (Universität Tübingen, DE)
  • Martin Grohe (HU Berlin, DE) [dblp]
  • Torben Hagerup (Universität Augsburg, DE) [dblp]
  • Michael Hallett (McGill University - Montreal, CA)
  • Edward A. Hirsch (Steklov Institute - St. Petersburg, RU) [dblp]
  • Michael Kaufmann (Universität Tübingen, DE) [dblp]
  • Johannes Köbler (HU Berlin, DE) [dblp]
  • Dieter Kratsch (University of Metz, FR) [dblp]
  • Klaus-Jörn Lange (Universität Tübingen, DE) [dblp]
  • Johann A. Makowsky (Technion - Haifa, IL) [dblp]
  • Catherine McCartin (Massey University, NZ) [dblp]
  • Haiko Müller (University of Leeds, GB) [dblp]
  • Matthias Müller-Hannemann (TU Darmstadt, DE) [dblp]
  • Rolf Niedermeier (Universität Jena, DE) [dblp]
  • Naomi Nishimura (University of Waterloo, CA) [dblp]
  • Andrzej Proskurowski (University of Oregon - Eugene, US) [dblp]
  • Prabhakar Ragde (University of Waterloo, CA)
  • Venkatesh Raman (Chennai Mathematical Institute, IN) [dblp]
  • Kenneth Regan (SUNY - Buffalo, US)
  • Klaus Reinhardt (Universität Tübingen, DE)
  • Mike Robson (University of Bordeaux, FR)
  • Frances A. Rosamond (University of Newcastle, AU) [dblp]
  • Peter Rossmanith (RWTH Aachen, DE) [dblp]
  • Marcus Schaefer (DePaul University - Chicago, US) [dblp]
  • Uwe Schöning (Universität Ulm, DE) [dblp]
  • Rainer Schuler (Universität Ulm, DE)
  • Detlef G. Seese (KIT - Karlsruher Institut für Technologie, DE)
  • Ewald Speckenmeyer (Universität Köln, DE) [dblp]
  • Ulrike Stege (University of Victoria, CA) [dblp]
  • Jan Arne Telle (University of Bergen, NO) [dblp]
  • Todd Wareham (Memorial University of Newfoundland, CA) [dblp]
  • Walker M. White (University of Dallas, US)
  • Gerhard J. Woeginger (TU Eindhoven, NL) [dblp]

Related Seminars
  • Dagstuhl Seminar 09511: Parameterized complexity and approximation algorithms (2009-12-13 - 2009-12-17) (Details)