TOP
Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Seminars
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Publishing
Within this website:
External resources:
dblp
Within this website:
External resources:
  • the dblp Computer Science Bibliography


Dagstuhl Seminar 14071

Graph Modification Problems

( Feb 09 – Feb 14, 2014 )

(Click in the middle of the image to enlarge)

Permalink
Please use the following short url to reference this page: https://www.dagstuhl.de/14071

Organizers

Contact



Schedule

Motivation

Many of the famous NP-complete graph problems can be characterized as graph modification problems; a few classical examples are Clique, Vertex Cover, Feedback Vertex Set, and Odd Cycle Transversal. A typical graph modification problem takes as input a graph G and an integer kand asks whether a graph satisfying some property can be obtained by applying at most k operations on G. Standard operations are vertex deletion, edge deletion, edge addition, edge contraction, and combinations of these; several other operations are also studied. To mention a few more of the resulting problems, Induced Subgraph Isomorphism, Subgraph Isomorphism, Minor Containment, Cluster Editing, Minimum Fill-in, Bandwidth, Treewidth, and Vertex Ranking can all be formulated as graph modification problems. These problems are motivated from various application fields, as biology (in particular phylogeny and DNA construction), data similarity in large sets, computer vision, sparse matrix computations, and image processing.

Although all of the above mentioned problems are NP-complete, they behave differently when they are attacked by various tools of coping with NP-completeness. Graph modification problems have traditionally been central in the field of parameterized algorithms. Furthermore, as graphs satisfying a given property form a graph class, there is a strong connection between graph modification problems and graph classes. Interestingly, some famous graph problems, like Vertex Ranking, correspond to graph modification problems into graph classes some of which have traditionally not been considered as important or large enough, like trivially perfect graphs.

The main objective of this seminar is to bring together experts within parameterized algorithms and experts within graph classes to join forces on graph modification problems. Both the field of graph classes and the field of parameterized algorithms have independently flourished and gained great interest and success during the last two decades. Many prominent researchers are working in both areas; however there is a great potential in bringing the experts of both fields together to work on important graph problems from the perspective of graph modification with the aim that several of the hard problems arising in real applications will eventually find practical solutions.

Focus will be given in particular to the following challenges:

  • Bring down the running time of best known algorithms on problems that can be formulated as graph modification problems. There has been very promising progress on some problems recently, like the running time of Feedback Vertex Set which has been successively improved over the last few years.
  • Provide new characterizations of famous graph modification problems that might help solving other problems. For example, in Minimum Fill-In the aim is to add as few edges as possible to the input graph G to make it chordal. The study of minimal triangulations that is inclusion minimal edge sets whose addition makes the graph chordal, has led to faster algorithms for Minimum Fill-In and Treewidth. Additionally, minimal triangulations have recently been used to give faster algorithms for seemingly unrelated problems such as Feedback Vertex Set, Planar Vertex Deletion and Induced Subgraph Isomorphism.
  • Provide new characterizations of important graph problems as graph modification problems. For some important graph parameters, like clique-width, we do not have any tractability results in general. This is closely connected to the fact that we do not yet have a characterization of clique-width as a graph modification problem.

For each of these mentioned challenges, we see a great potential for important new results along the lines of the mentioned examples.


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.

Copyright Hans L. Bodlaender, Pinar Heggernes, and Daniel Lokshtanov

Participants
  • Isolde Adler (Goethe-Universität - Frankfurt a. M., DE) [dblp]
  • Rémy Belmonte (Kyoto University, JP) [dblp]
  • Hans L. Bodlaender (Utrecht University, NL & Technical University Eindhoven, NL) [dblp]
  • Andreas Brandstädt (Universität Rostock, DE) [dblp]
  • Yixin Cao (Hungarian Academy of Sciences - Budapest, HU) [dblp]
  • Derek G. Corneil (University of Toronto, CA) [dblp]
  • Marek Cygan (University of Warsaw, PL) [dblp]
  • Tinaz Ekim (Bogaziçi University - Istanbul, TR) [dblp]
  • Henning Fernau (Universität Trier, DE) [dblp]
  • Fedor V. Fomin (University of Bergen, NO) [dblp]
  • Archontia C. Giannopoulou (Durham University, GB) [dblp]
  • Petr A. Golovach (University of Bergen, NO) [dblp]
  • Martin Charles Golumbic (Haifa University, IL) [dblp]
  • Alexander Grigoriev (Maastricht University, NL) [dblp]
  • Pinar Heggernes (University of Bergen, NO) [dblp]
  • Bart Jansen (University of Bergen, NO) [dblp]
  • Mamadou Moustapha Kanté (University Blaise Pascal - Aubiere, FR) [dblp]
  • Eun Jung Kim (University Paris-Dauphine, FR) [dblp]
  • Dieter Kratsch (University of Metz, FR) [dblp]
  • Stefan Kratsch (TU Berlin, DE) [dblp]
  • O-joung Kwon (KAIST - Daejeon, KR) [dblp]
  • Van Bang Le (Universität Rostock, DE) [dblp]
  • Daniel Lokshtanov (University of Bergen, NO) [dblp]
  • Dániel Marx (Hungarian Academy of Sciences - Budapest, HU) [dblp]
  • Paul Medvedev (Pennsylvania State University - University Park, US) [dblp]
  • Daniel Meister (Universität Trier, DE) [dblp]
  • George B. Mertzios (Durham University, GB) [dblp]
  • Martin Milanic (University of Primorska, SI) [dblp]
  • Neeldhara Misra (Indian Institute of Science, IN) [dblp]
  • Haiko Müller (University of Leeds, GB) [dblp]
  • André Nichterlein (TU Berlin, DE) [dblp]
  • Rolf Niedermeier (TU Berlin, DE) [dblp]
  • Charis Papadopoulos (University of Ioannina, GR) [dblp]
  • Christophe Paul (University of Montpellier 2, FR) [dblp]
  • Daniel Paulusma (Durham University, GB) [dblp]
  • Marcin Pilipczuk (University of Bergen, NO) [dblp]
  • Michal Pilipczuk (University of Bergen, NO) [dblp]
  • Andrzej Proskurowski (University of Oregon - Eugene, US) [dblp]
  • Dieter B. Rautenbach (Universität Ulm, DE) [dblp]
  • Saket Saurabh (The Institute of Mathematical Sciences, IN) [dblp]
  • Dimitrios M. Thilikos (University of Athens, GR) [dblp]
  • Pim van 't Hof (University of Bergen, NO) [dblp]
  • Erik Jan van Leeuwen (MPI für Informatik - Saarbrücken, DE) [dblp]
  • Kristina Vuskovic (University of Leeds, GB) [dblp]

Related Seminars
  • Dagstuhl Seminar 99231: Graph Decompositions and Algorithmic Applications (1999-06-06 - 1999-06-11) (Details)
  • Dagstuhl Seminar 01251: Graph Decompositions and Algorithmic Applications (2001-06-17 - 2001-06-22) (Details)
  • Dagstuhl Seminar 04221: Robust and Approximative Algorithms on Particular Graph Classes (2004-05-23 - 2004-05-28) (Details)
  • Dagstuhl Seminar 07211: Exact, Approximative, Robust and Certifying Algorithms on Particular Graph Classes (2007-05-20 - 2007-05-25) (Details)
  • Dagstuhl Seminar 11182: Exploiting graph structure to cope with hard problems (2011-05-01 - 2011-05-06) (Details)

Keywords
  • Graph classes
  • parameterized algorithms
  • exact exponential time algorithms
  • graph embedding
  • graph editing