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
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Within this website:
External resources:
Within this website:
External resources:
  • the dblp Computer Science Bibliography

Dagstuhl Seminar 11182

Exploiting graph structure to cope with hard problems

( May 01 – May 06, 2011 )

(Click in the middle of the image to enlarge)

Please use the following short url to reference this page:





One of the main goals of this Dagstuhl seminar was to gather experts with a common focus on graph algorithms but with various specializations to attack NP-hard graph problems using the structure of the input graph. This goal was achieved to a great extent, as the number of participants of our seminar was above the limit that was given beforehand. The seminar was granted space for $30$ participants, and we had $35$ participants on site. Still there were many experts and young researchers in the field that would like to come but that could not be invited due to lack of space. The participants that came to our seminar were from the following countries: 9 from Germany, 7 from USA, 5 from France, 4 from Israel, 4 from Norway, 1 from Canada, 1 from Korea, 1 from Taiwan, 1 from Turkey, 1 from Greece, and 1 from Great Britain.

By bringing together experts with backgrounds in graph classes, optimization, width parameters, and parameterized and exact computing, our aim was that several of the hard problems arising in real applications would eventually find practical solutions. The seminar program was divided into two parts each day of the seminar: (1) presentation of new results, and (2) posing and discussions on new problems. Each of the presented new results and the discussed problems will be explained in detail in the sections below. In this section, we briefly summarize the program of the seminar.

On the first day of the seminar, Jesper Nederlof presented new results on solving connectivity problems parameterized by treewidth in single exponential time, Charis Papadopoulos presented new results on characterizing the linear clique-width of a class of graphs by forbidden induced subgraphs, Yngve Villanger presented new kernelization and approximation results on minimum fill-in of sparse graphs, and Martin Milanic presented new results on hereditary efficiently dominatable graphs. During the problem solving session of the first day, Pinar Heggernes posed a problem on dense subgraphs on proper interval graphs, Andreas Brandstädt and Christian Hundt posed problems on k-leaf powers, Dieter Rautenbach posed a problem on 2-domination on strongly chordal graphs, Pavol Hell asked which problems that are hard on general digraphs become efficiently solvable on interval digraphs, and Feodor Dragan introduced and asked questions about the short fill-in problem.

On the second day of the seminar, Ann Trenk presented a survey on the total linear discrepancy of a poset, Elad Cohen presented new results on vertex intersection graphs of paths on a grid, Yahav Nussbaum presented new results on the recognition of probe proper interval graphs, and Tinaz Ekim presented a survey on polar graphs. During the problem solving session of the second day, Daniel Lokshtanov posed a problem on map graphs, Christian Hundt gave more details on his problem on k-leaf powers, Martin Golumbic posed a problem on the recognition of one-bend EPG and VPG graphs, and Sang-il Oum posed a problem on Bott equivalence between directed acyclic graphs.

On the third day of the seminar, Dieter Rautenbach presented new results on unit interval graphs, R. Sritharan presented new results on finding a sun in graphs, Bernard Ries presented new vertices on coloring vertices of triangle-free graphs, and Wen-Lian Hsu presented new results on PC-trees and planar graphs. In the afternoon of the third day, there was an excursion to Trier and a hike in the close by surroundings of Dagstuhl area.

On the fourth day of the seminar, Pavol Hell presented new results on partitioning chordal graphs, Pim van 't Hof presented new results on contracting graphs to paths and trees, Daniel Lokshtanov presented new results on contracting graphs to bipartite graphs, and Frédéric Maffray presented new results on 3-colorable P_5-free graphs. During the problem solving session of the fourth day, Daniel Lokshtanov posed a problem on the parameterized complexity of protein folding, Yngve Villanger posed a question about forbidden induced subgraphs of circular arc graphs, Christophe Paul asked a question on recognizing circle graphs, and Van Bang Le posed a problem on modified circle graphs.

On the fifth day of the seminar, Feodor Dragan presented new results on graph classes, tree decomposition and approximation algorithms, Elias Dahlhaus presented new results on minimal fill-in ordering of planar graphs in linear time, and Christian Hundt presented new results on the dominating induced matching problem for hole-free graphs. The seminar ended with a brief discussion on all the presented results.

  • Andreas Brandstädt (Universität Rostock, DE) [dblp]
  • Elad Cohen (Haifa University, IL)
  • Elias Dahlhaus (DB Systems GmbH - Frankfurt, DE) [dblp]
  • Feodor F. Dragan (Kent State University, US)
  • Tinaz Ekim (Bogaziçi University - Istanbul, TR) [dblp]
  • Elaine M. Eschen (West Virginia University - Morgantown, US)
  • Martin Charles Golumbic (Haifa University, IL) [dblp]
  • Pinar Heggernes (University of Bergen, NO) [dblp]
  • Pavol Hell (Simon Fraser University - Burnaby, CA) [dblp]
  • Wen-Lian Hsu (Academica Sinica - Taipei, TW)
  • Christian Hundt (Universität Rostock, DE)
  • Ekkehard Köhler (BTU Cottbus, DE) [dblp]
  • Dieter Kratsch (University of Metz, FR) [dblp]
  • Van Bang Le (Universität Rostock, DE) [dblp]
  • Daniel Lokshtanov (University of California - San Diego, US) [dblp]
  • Frédéric Maffray (CNRS - Grenoble, FR) [dblp]
  • Ross McConnell (Colorado State University, US)
  • Daniel Meister (Universität Trier, DE) [dblp]
  • Martin Milanic (University of Primorska, SI) [dblp]
  • Haiko Müller (University of Leeds, GB) [dblp]
  • Jesper Nederlof (University of Bergen, NO) [dblp]
  • Ragnar Nevries (Universität Rostock, DE)
  • Yahav Nussbaum (Tel Aviv University, IL) [dblp]
  • Sang-il Oum (KAIST - Daejeon, KR) [dblp]
  • Charis Papadopoulos (University of Ioannina, GR) [dblp]
  • Christophe Paul (University of Montpellier 2, FR) [dblp]
  • Andrzej Proskurowski (University of Oregon - Eugene, US) [dblp]
  • Dieter B. Rautenbach (Universität Ulm, DE) [dblp]
  • Bernard Ries (University Paris-Dauphine, FR) [dblp]
  • R. Sritharan (University of Dayton, US)
  • Ioan Todinca (University of Orleans, FR) [dblp]
  • Ann Trenk (Wellesley College, US)
  • Pim van 't Hof (University of Bergen, NO) [dblp]
  • Yngve Villanger (University of Bergen, NO) [dblp]
  • Egon Wanke (Heinrich-Heine-Universität Düsseldorf, DE)

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 14071: Graph Modification Problems (2014-02-09 - 2014-02-14) (Details)

  • data structures
  • algorithms
  • complexity
  • networks

  • Graph classes
  • width parameters
  • approximation
  • parameterized and exact algorithms