https://www.dagstuhl.de/07281

July 8 – 13 , 2007, Dagstuhl Seminar 07281

Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs

Organizers

Erik D. Demaine (MIT – Cambridge, US)
Gregory Z. Gutin (Royal Holloway University of London, GB)
Dániel Marx (Budapest University of Technology & Economics, HU)
Ulrike Stege (University of Victoria, CA)


The workshop is supported by:

  •   Klaus Tschira Stiftung
  •   Schloss Dagstuhl - Leibniz-Zentrum für Informatik

For support, please contact

Dagstuhl Service Team

Documents

Dagstuhl Seminar Proceedings DROPS
List of Participants

Summary

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.

Classification

  • Data Structures / Algorithms / Complexity
  • Networks
  • Optimization / Scheduling

Keywords

  • Fixed parameter tractable
  • Graphs
  • Digraphs
  • Hypergraphs

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.