http://www.dagstuhl.de/11182

### 01. – 06. Mai 2011, Dagstuhl Seminar 11182

# Exploiting graph structure to cope with hard problems

## Organisatoren

Andreas Brandstädt (Universität Rostock, DE)

Martin Charles Golumbic (Haifa University, IL)

Pinar Heggernes (University of Bergen, NO)

Ross McConnell (Colorado State University, US)

## Auskunft zu diesem Dagstuhl Seminar erteilt

## Dokumente

Dagstuhl Report, Volume 1, Issue 5

Teilnehmerliste

Gemeinsame Dokumente

Programm des Dagstuhl Seminars [pdf]

## Summary

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.

## Dagstuhl Seminar Series

- 14071: "Graph Modification Problems" (2014)
- 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)

## Classification

- Data Structures
- Algorithms
- Complexity
- Networks

## Keywords

- Graph classes
- Width parameters
- Approximation
- Parameterized and exact algorithms