http://www.dagstuhl.de/14071

# Graph Modification Problems

## Organisatoren

Hans L. Bodlaender (Utrecht University, NL & Technical University Eindhoven, NL)
Pinar Heggernes (University of Bergen, NO)
Daniel Lokshtanov (University of Bergen, NO)

## Summary

A surprisingly high number of the interesting computational problems arising from theory and applications can be formulated as graph modification problems. Here we are given as input a graph G, and the goal is to apply certain operations on G (such as vertex deletions, edge deletions, additions or contractions) in order to obtain a graph H with some particular property. For an example the classical Vertex Cover problem can be formulated as trying to change G into an edgeless graph by performing the minimum possible number of vertex deletions. The Cluster Editing problem is to change G into a disjoint union of cliques with a minimum number of edge deletions or additions. Graph modification problems have been studied quite extensively, and both algorithms for these problems and structural aspects have been thoroughly explored.

Graph modification problems have received a significant amount of attention from the perspective of Parameterized Complexity. In parameterized complexity input comes with a parameter k and the goal is to design fixed parameter tractable algorithms, i.e. algorithms with running time f(k)n^{O(1) for some, hopefully not too fast growing function f. The parameter k can be the size of the solution sought for, or it could be a number describing how structured the input instance is. For an example k could be the treewidth of the input graph. Over the last few years, our understanding of the parameterized complexity of graph modification problems has greatly improved. Fixed parameter tractable algorithms have been found for a number of fundamental graph modification problems. For several problems, surprising new algorithms with subexponential (2^{o(k)}) dependence on k have been developed.

There is a strong connection between graph modification problems and graph classes. A graph class is simply a set of graphs satisfying some common properties. Thus many, if not all, graph modification problems can be phrased as modifying the input graph G by as few operations as possible to make it fit into a particular graph class. There is a large and active Graph Classes research community that primarily investigates how restricting the input graph to a particular graph class affects the computational complexity of computational problems. In the setting of graph modification problems we have no restrictions on the input graph, but the problem definitions dictate which graph class the output graph should belong to. The main objective of the seminar was to bring together experts within Parameterized Algorithms and experts within Graph Classes to join forces on graph modification problems. We also invited experts from related areas, such as Structural Graph Theory and Bioinformatics. Structural graph theory, in order to learn of the new powerful graph theoretic tools being developed, and hopefully to apply them on graph modification problems. Bioinformatics, in order to better understand the relationship between the idealized models we study and real-world applications of graph algorithms.

The scientific program of the seminar consisted of 21 talks. 4 of these talks were longer (45 or 90 minute) presentations covering some of the most exciting developments on graph modification problems and related areas. We had one long talk for each of the main topics covered by the seminar. On Monday, Marcin and Michal Pilipczuk gave a joint 90 minute talk ("Subexponential parameterized complexity of completion problems") on parameterized algorithms. On Tuesday, Paul Medvedev gave a 45 minute talk ("An introduction to genome assembly and its relation to problems on graphs") showcasing how graph algorithms can be used in Bioinformatics applications. On Wednsday, Kristina Vuskovic gave a 45 minute presentation ("Weighted Independent Set in bull-free graphs") about how deep structure theorems can be useful in algorithm design, and on Thursday, Andreas Brandstädt gave a presentation ("Clique separator decomposition for a subclass of hole-free graphs") on graph classes. We believe that the invited talks were a good starting point for cross-community collaboration. The remaining talks were 30 or 35 minute presentations on recent research of the participants. We made a point out of having fewer short talks, in order to leave more time for individual discussions and collaboration in groups, as well as for open problem sessions. The idea was to reserve almost all of the time between lunch and dinner for research. This was very well received by the participants. There were 3 fruitful open problem sessions, on Monday, Tuesday and Thursday. Notes on the presented problems can be found in this report.

Creative Commons BY 3.0 Unported license
Hans L. Bodlaender, Pinar Heggernes, and Daniel Lokshtanov

## Keywords

• Graph classes
• Parameterized algorithms
• Exact exponential time algorithms
• Graph embedding
• Graph editing

## Buchausstellung

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.