The aim of this seminar was to bring together experts working on exact, approximative, robust and certifying algorithms on particular graph classes. Given the fast advances in various areas of graph algorithms on particular graph classes 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 and inspiring workshop atmosphere that Dagstuhl always offers.

There was a strong interaction and healthy exchange of ideas which resulted in successful applications of exact, approximative, robust and certifying graph algorithms; in particular, the seminar dealt with the following topics and their interactions:

• Exact algorithms require that the algorithm provides exactly the result requested. The approach is interesting for NP-hard problems. Two different approaches are exponential-time algorithms and fixed-parameter algorithms. Exponential-time algorithms must solve the problem for all possible inputs exactly. The goal is to obtain an exponential running time being as small as possible as described in the important survey [G. Woeginger, Exact algorithms for NP-hard problems: A survey. In: Combinatorial Optimization - Eureka! You shrink!. M. Juenger, G. Reinelt and G. Rinaldi (eds.). LNCS 2570, Springer, 2003, pp 185-207.] Fixed-parameter algorithms are supposed to solve the problem exactly as long as the result is not larger than the given value of the parameter. In many cases fixed-parameter algorithms are tuned for ``small parameters''. Fixed-parameter algorithms have been studied extensively by Downey and Fellows [Fixed parameter complexity, Springer, 1999], and recent monographs by Niedermeier, and by Flum and Grohe.
• For approximative algorithms, two new concepts shall be discussed, which improve the running time considerably. The first one deals with parameterized complexity, where various parts of the input such as the number n of vertices or the size k of a maximum independent set play the role of a parameter and the running time of the algorithm is optimized with respect to the parameters. This approach is promising for polynomial approximation schemes. The second one concerns methods of (non-)linear programming for graph-theoretic problems. There are various optimization problems such as special network-flow problems or determining a maximum independent set in a perfect graph which have polynomial time algorithms but these are far from being really efficient since the algorithms have to solve large linear programming instances. The algorithms become much more efficient, however, if only approximative solutions (with good factors) are required and this is done using methods of (non-)linear programming.
• A robust algorithm for a graph class C and an algorithmic problem Pi is always giving a correct answer: If the input graph G is in the class C then the problem Pi will be correctly solved, and if G is not in C then either Pi will be correctly solved or the algorithm finds out that G is not in C. In both cases, the answer is correct, and the algorithm avoids recognizing C. This can be of big advantage if recognizing C is NP-complete or even harder. There are various degrees of verification in the case that G is not in C; a witness for this is desirable.
• Certifying recognition algorithms provide a proof respectively certificate for membership and non membership. Certifying algorithms are highly desirable in practice since implementations of correct algorithms may have bugs. Furthermore since the software producing the certificates may have bugs, the certificates have to be authenticated, and this should use a simple and efficient algorithm. A good example is the linear time certifying recognition algorithm for interval graphs [D. Kratsch, R. M. McConnell, K. Mehlhorn, J. Spinrad, Certifying algorithms for recognizing interval graphs and permutation graphs, SODA 2003: 158-167].

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.