http://www.dagstuhl.de/07281

08. – 13. Juli 2007, Dagstuhl Seminar 07281

Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs

Organisatoren

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)


Der Workshop wird unterstützt von:

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

Auskunft zu diesem Dagstuhl Seminar erteilt

Dagstuhl Service Team

Dokumente

Dagstuhl Seminar Proceedings DROPS
Teilnehmerliste

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

Buchausstellung

Bücher der Teilnehmer 

Buchausstellung im Erdgeschoss der Bibliothek

(nur in der Veranstaltungswoche).

Dokumentation

In der Reihe Dagstuhl Reports werden alle Dagstuhl-Seminare und Dagstuhl-Perspektiven-Workshops dokumentiert. Die Organisatoren stellen zusammen mit dem Collector des Seminars einen Bericht zusammen, der die Beiträge der Autoren zusammenfasst und um eine Zusammenfassung ergänzt.

 

Download Übersichtsflyer (PDF).

Publikationen

Es besteht weiterhin die Möglichkeit, eine umfassende Kollektion begutachteter Arbeiten in der Reihe Dagstuhl Follow-Ups zu publizieren.

Dagstuhl's Impact

Bitte informieren Sie uns, wenn eine Veröffentlichung ausgehend von
Ihrem Seminar entsteht. Derartige Veröffentlichungen werden von uns in der Rubrik Dagstuhl's Impact separat aufgelistet  und im Erdgeschoss der Bibliothek präsentiert.