http://www.dagstuhl.de/14071

### February 9 – 14 , 2014, Dagstuhl Seminar 14071

# Graph Modification Problems

## Organizers

Hans L. Bodlaender (Utrecht University, NL & Technical University Eindhoven, NL)

Pinar Heggernes (University of Bergen, NO)

Daniel Lokshtanov (University of Bergen, NO)

## For support, please contact

## Documents

Dagstuhl Report, Volume 4, Issue 2

Aims & Scope

List of Participants

Shared Documents

Dagstuhl's Impact: Documents available

Dagstuhl Seminar Schedule [pdf]

## 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.

**License**

Creative Commons BY 3.0 Unported license

Hans L. Bodlaender, Pinar Heggernes, and Daniel Lokshtanov

## Dagstuhl Seminar Series

- 11182: "Exploiting graph structure to cope with hard problems" (2011)
- 07211: "Exact, Approximative, Robust and Certifying Algorithms on Particular Graph Classes " (2007)
- 04221: "Robust and Approximative Algorithms on Particular Graph Classes" (2004)
- 01251: "Graph Decompositions and Algorithmic Applications" (2001)
- 99231: "Graph Decompositions and Algorithmic Applications" (1999)

## Keywords

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