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

Dagstuhl Service Team

Documents

Dagstuhl Report, Volume 4, Issue 2 Dagstuhl Report
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

Keywords

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

Book exhibition

Books from the participants of the current Seminar 

Book exhibition in the library, ground floor, during the seminar week.

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.