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 07281

Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs

( Jul 08 – Jul 13, 2007 )

(Click in the middle of the image to enlarge)

Please use the following short url to reference this page:



Fixed-parameter algorithmics (FPA) is a relatively new approach for dealing with NP-hard computational problems. In the framework of FPA we try to introduce a parameter k such that the problem in hand can be solved in time O(f(k)nc), where f(k) is an arbitrary computable function, n is the size of the problem and c is a constant not dependent of n or k. When a parameterized problem P admits an algorithm of running time O(f(k)nc), P is called fixed-parameter tractable (FPT). The ultimate goal is to obtain such f(k) and c that for small or even moderate values of k the problem under consideration can be completely solved in a reasonable amount of time. Many practical problems can now be tackled using FPA.

The possibility of deep and algorithmically useful combinatorial structure theory seems to be closely allied with FPT - in various combinatorial settings these two different aspects, the one mathematical and the other algorithmic, seem to go together. The parameterized problem Graph Minor Testing is FPT, and exposes in its allied structure theory, with such fundamental structural parameters such as treewidth, the kinds of connections between parameterized structure theory and FPA that the workshop will explore, encourage and develop by bringing together two kinds of researchers: (1) structure-theory minded FPT algorithmists, and (2) practical computing practitioners who have been grappling with real-world input-structure issues in sophisticated and effective ways (especially: by data-reduction and pre-processing).

Beyond treewidth, which has turned out to be a surprisingly universal structural parameter, are a collection of newer related notions which are currently of intense research interest: cliquewidth of graphs, hypertreewidth of hypergraphs and various parameters measuring near-acyclicity of hypergraphs. The latter are of relevance to the natural input distributions in database and constraint satisfaction problems, and it is a major concern of the workshop to motivate and explore to what extent the successful structure theory and FPA of treewidth, etc. of graphs can be lifted to the setting of hypergraphs.

Although graphs have proven to be a hugely flexible computational modeling tool, and the structure theory and allied FPA of graphs has developed strongly, very little can yet be said for digraphs, even though in the grand scheme of things, digraphs are the more important modeling tool: the entire picture for digraphs in terms of structure theory and FPA has lagged far behind graphs. Some of the most important open problems in concrete FPA involve digraphs (e.g., the Directed Feedback Vertex Set problem that has a vast range of potential important applications, and is widely conjectured to be FPT), yet the appropriate combinatorial structure theory is so far undeveloped.

During the 5 days of the conference, 23 talks were given by the participants. Two of these talks were 50-minute surveys given by founders of the field: Mike Fellows started the workshop by reviewing the latest technical and methodological developments and Mike Langston reported on recent algorithmic applications in computational biology. As a highlight of the seminar, Jianer Chen and Igor Razgon presented their very recent work on the Directed Feedback Vertex Set problem. The complexity status of this very important problem was open for 15 years or so, until two independent groups of researchers proved its fixed-parameter tractability earlier this year. The technical reports of both groups are available in this volume. The solution of the problem required a clever mix of old and new ideas. In recent years the field witnessed a more systematic identification, study, and dissemination of algorithmic ideas, leading to significant new results. There is no doubt that this progress was helped enormously by meetings such as the previous Dagstuhl seminars.

The talks left plenty of time for discussion in the afternoon. An open problem session was held on Monday. Problems raised there were discussed by different groups throughout the seminar.

  • Faisal N. Abu-Khzam (Lebanese American University, LB) [dblp]
  • Isolde Adler (HU Berlin, DE) [dblp]
  • Guoqiang Bai (Universität Trier, DE)
  • Jorgen Bang-Jensen (University of Southern Denmark - Odense, DK)
  • Jianer Chen (Texas A&M University - College Station, US) [dblp]
  • Yijia Chen (Shanghai Jiao Tong University, CN) [dblp]
  • Erik D. Demaine (MIT - Cambridge, US) [dblp]
  • Michael Dom (Universität Jena, DE)
  • Patricia Evans (University of New Brunswick, CA)
  • Michael R. Fellows (University of Newcastle, AU) [dblp]
  • Henning Fernau (Universität Trier, DE) [dblp]
  • Jiong Guo (Universität Jena, DE) [dblp]
  • Gregory Z. Gutin (Royal Holloway University of London, GB) [dblp]
  • MohammadTaghi Hajiaghayi (MIT - Cambridge, US) [dblp]
  • Frederic Havet (INRIA Sophia Antipolis - Méditerranée, FR)
  • Petr Hlinený (Masaryk University - Brno, CZ) [dblp]
  • Falk Hüffner (Universität Jena, DE) [dblp]
  • Marcin Kaminski (University of Brussels, BE) [dblp]
  • Iyad A. Kanj (DePaul University - Chicago, US) [dblp]
  • Dieter Kratsch (University of Metz, FR) [dblp]
  • Stephan Kreutzer (HU Berlin, DE) [dblp]
  • Andrei Krokhin (Durham University, GB) [dblp]
  • Michael A. Langston (University of Tennessee, US)
  • Barnaby Martin (Durham University, GB) [dblp]
  • Dániel Marx (Budapest University of Technology & Economics, HU) [dblp]
  • Luke Mathieson (Durham University, GB)
  • Moritz Müller (Universität Freiburg, DE) [dblp]
  • Sang-il Oum (University of Waterloo, CA) [dblp]
  • Oriana Ponta (Universität Heidelberg, DE)
  • Daniel Raible (Universität Trier, DE)
  • Venkatesh Raman (Chennai Mathematical Institute, IN) [dblp]
  • Igor Razgon (University College Cork, IE) [dblp]
  • Klaus Reinhardt (Universität Tübingen, DE)
  • Peter Rossmanith (RWTH Aachen, DE) [dblp]
  • Marko Samer (Durham University, GB)
  • Saket Saurabh (University of Bergen, NO) [dblp]
  • Allan Scott (University of Victoria, CA)
  • Detlef G. Seese (KIT - Karlsruher Institut für Technologie, DE)
  • Somnath Sikdar (Chennai Mathematical Institute, IN) [dblp]
  • Ulrike Stege (University of Victoria, CA) [dblp]
  • Stefan Szeider (Durham University, GB) [dblp]
  • Meike Tewes (Deutsche Telekom - Bonn, DE)
  • Dimitrios M. Thilikos (University of Athens, GR) [dblp]
  • Iris van Rooij (TU of Eindhoven, NL) [dblp]
  • Todd Wareham (Memorial University of Newfoundland, CA) [dblp]
  • Anders Yeo (Royal Holloway University of London, GB) [dblp]

  • data structures / algorithms / complexity
  • networks
  • optimization / scheduling

  • fixed parameter tractable
  • graphs
  • digraphs
  • hypergraphs