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.

• 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]