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

## Documents

## 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*)*n*^{c}), 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*)*n*^{c}), 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