Robust and Approximative Algorithms on Particular Graph Classes

Summary

The aim of this seminar was to bring together experts working on robust as well as on approximative graph algorithms. Given the fast advances in various areas of graph algorithms on particular graph classes that we have witnessed in the past few years, we believe that it was very important to offer researchers in these areas a forum for the exchange of ideas in the relaxed workshop-like atmosphere that Dagstuhl always offers.

There was a strong interaction and healthy exchange of ideas which resulted in successful applications of robust and approximative graph algorithms; in particular, the seminar had the following aims:

• discussing new graph classes where the recognition complexity of a graph class is harder than solving certain basic graph problems on the class;
• new structural insights by studying the modular and homogeneous decomposition as well as treewidth and clique-width of important graph classes, and the application of these results to the design of robust graph algorithms;
• parameterized complexity and its influence to the design of efficient approximative algorithms;
• solving graph problems approximatively by using (non-)linear programming for graph classes where the problems can be solved in polynomial time but the time bound is poor (e.g. network design problems, Maximum Independent Set for perfect graphs).

The most outstanding result of the discussions during the seminar was the proof of the Seese conjecture by combining results of Courcelle and Sang-il Oum.

As always, Schloss Dagstuhl and its stuff provided a very convenient and stimulating environment. The organizers wish to thank all those who helped to make the seminar a fruitful research experience.