TOP
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
Seminars
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Publishing
Within this website:
External resources:
dblp
Within this website:
External resources:
  • the dblp Computer Science Bibliography


Dagstuhl Seminar 05301

Exact Algorithms and Fixed-Parameter Tractability

( Jul 24 – Jul 29, 2005 )


Permalink
Please use the following short url to reference this page: https://www.dagstuhl.de/05301

Organizers




Summary

It seems that by now almost everybody in our community has accepted that P≠NP holds true, although we do not have the slightest idea how to prove it. Regardless, P≠NP means that there are no polynomial time algorithms for NP-hard problems, and that super-polynomial time algorithms are the best we can hope for when dealing with exact algorithms for NP-hard problems.

Recently, there have been some fascinating activities on exact algorithms. For example, there has been a long sequence of papers on exact algorithms for 3-satisfiability. The current best algorithm for this problem is due to Iwama and Tamaki (2003) and needs roughly 1.324n time for instances with n variables. Fomin and Kratsch (September 2003) have just developed a 1.993n exact algorithm for determining the tree-width of an n-vertex graph - this is clearly not the last result on this problem. Fedin and Kulikov (2002) gave an exact 2m/4 algorithm for the Max-Cut problem on graphs with m edges. There also has been a number of ever improving algorithms for the Vertex Cover problem; the current best is from Chen, Kanj, and Jia (2001) and it finds a Vertex Cover of size k in a graph of size n in time 1.285k+kn .

However, many very interesting questions are still wide open and have received little if any attention. We mention just two examples here:

  • Held and Karp (1962) designed a dynamic programming algorithm for the n -city traveling salesman problem with a running time of roughly 2n . This running time has not been improved in more than 40 years.
  • Nesetril and Poljak (1985) observed that a simple algorithm based on matrix multiplication finds a clique of size k in an n-vertex graph in time n0.79k . No improvement has been made since then.

More qualitatively, we ask if there are algorithms solving the satisfiability problem or the traveling salesman problem in time 2o(n) or the clique problem in time no(k) . Very little is known about such lower bound questions.

The idea of fixed-parameter tractability is to approach hard algorithmic problems by isolating problem parameters that can be expected to be small in certain applications and then develop algorithms that are polynomial except for an arbitrary dependence on the parameter. More precisely, a problem is fixed-parameter tractable if its running time is f(k)p(n) , where f is an arbitrary function and p a polynomial. Since the choice of suitable parameters allows for a great flexibility, fixed-parameter algorithms have found their way into practical applications such diverse as computational biology, database systems, computational linguistics, and automated verification. The algorithmic methods developed in this area are not far from those used in the exact algorithms mentioned above. As a matter of fact, the fast algorithms for Vertex Cover have been developed in the context of fixed-parameter tractability. But beyond these algorithmic results, parameterized complexity also offers a well developed theory of intractability, and this theory may provide us with the right tools to systematically approach a theory of lower bounds for exact algorithms. For example, parameterized complexity allows us to establish exponential lower bounds on hard problems, modulo complexity assumptions. Indeed, recent work has substantiated the fact that this approach has deep links with the existence of feasible PTAS's, and limited nondeterminism; so we see the exciting emerging interplay between a number of hitherto unlinked groups of researcher.

To summarize, the area of Exact Algorithms is still in a rudimentary stage, but it is full of fascinating and difficult open problems. Fixed-parameter tractability is a branch of algorithms and complexity theory that seems very well suited to approach some of these questions. Connections between the two areas have recently evolved, ranging from very practical questions in algorithms design to the fundamental complexity theoretic problems.

The Seminar

The seminar brought together leading researchers from exact algorithms and parameterized complexity theory. If not before, it became very clear during the seminar that the areas are quickly growing together. Topics of the seminar ranged from very practical aspects of algorithm engineering for applications in computational biology to theoretical and mathematical topics such structural parameterized complexity and matroid theory. The technical program consisted of 7 invited one hour talks and 25 half hour talks. There will be a special issue of the journal Theory of Computing Systems , edited by Rod Downey, devoted to work arizing from this seminar.

The main topics of the seminar can be grouped as follows:

  • Better Exact and Parameterized Algorithms
  • Applications and Algorithm Engineering
  • Decompositions of Graphs and Matroids and their Algorithmic Applications
  • New Developments in Parameterized Complexity

Participants
  • Faisal N. Abu-Khzam (Lebanese American University, LB) [dblp]
  • Albert Atserias (UPC - Barcelona, ES) [dblp]
  • Jonathan Buss (University of Waterloo, CA)
  • Jianer Chen (Texas A&M University - College Station, US) [dblp]
  • Yijia Chen (HU Berlin, DE) [dblp]
  • Amin Coja-Oghlan (HU Berlin, DE) [dblp]
  • Rodney Downey (Victoria University of Wellington, NZ) [dblp]
  • Michael R. Fellows (University of Newcastle, AU) [dblp]
  • Henning Fernau (University of Hertfordshire, GB) [dblp]
  • Rudolf Fleischer (Fudan University - Shanghai, CN) [dblp]
  • Jörg Flum (Universität Freiburg, DE) [dblp]
  • Fedor V. Fomin (University of Bergen, NO) [dblp]
  • Andreas Goerdt (TU Chemnitz, DE) [dblp]
  • Martin Grohe (HU Berlin, DE) [dblp]
  • Magdalena Grüber (HU Berlin, DE)
  • Jiong Guo (Universität Jena, DE) [dblp]
  • Gregory Z. Gutin (Royal Holloway University of London, GB) [dblp]
  • Petr Hlinený (TU - Ostrava, CZ) [dblp]
  • Thomas Hofmeister (TU Dortmund, DE)
  • Falk Hüffner (Universität Jena, DE) [dblp]
  • Cor Hurkens (TU Eindhoven, NL)
  • Kazuo Iwama (Kyoto University, JP) [dblp]
  • Iyad A. Kanj (DePaul University - Chicago, US) [dblp]
  • Walter Kern (University of Twente, NL)
  • Joachim Kneis (RWTH Aachen, DE) [dblp]
  • Johannes Köbler (HU Berlin, DE) [dblp]
  • Dieter Kratsch (University of Metz, FR) [dblp]
  • Stephan Kreutzer (HU Berlin, DE) [dblp]
  • Andrei Krokhin (Durham University, GB) [dblp]
  • Alexander S. Kulikov (Steklov Institute - St. Petersburg, RU) [dblp]
  • Michael A. Langston (University of Tennessee, US)
  • Dániel Marx (Budapest University of Technology & Economics, HU) [dblp]
  • Catherine McCartin (Massey University, NZ) [dblp]
  • Wolfgang Merkle (Universität Heidelberg, DE) [dblp]
  • Juan Andrés Montoya (Universität Freiburg, DE)
  • Moritz Müller (Universität Freiburg, DE) [dblp]
  • Rolf Niedermeier (Universität Jena, DE) [dblp]
  • Naomi Nishimura (University of Waterloo, CA) [dblp]
  • Sang-il Oum (Princeton University, US) [dblp]
  • Stefan Porschen (Universität Köln, DE)
  • Prabhakar Ragde (University of Waterloo, CA)
  • 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]
  • Ingo Schiermeyer (TU Bergakademie Freiberg, DE) [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)
  • Ulrike Stege (University of Victoria, CA) [dblp]
  • Stefan Szeider (Durham University, GB) [dblp]
  • Till Tantau (TU Berlin, DE) [dblp]
  • Dimitrios M. Thilikos (UPC - Barcelona, ES) [dblp]
  • Ioan Todinca (University of Orleans, FR) [dblp]
  • Iris van Rooij (TU Eindhoven, NL) [dblp]
  • Xinhui Wang (University of Twente, NL)
  • Mark Weyer (Universität Freiburg, DE)
  • Geoff Whittle (Victoria University of Wellington, NZ)
  • Ryan Williams (Carnegie Mellon University - Pittsburgh, US) [dblp]
  • Gerhard J. Woeginger (TU Eindhoven, NL) [dblp]