https://www.dagstuhl.de/07211

May 20 – 25 , 2007, Dagstuhl Seminar 07211

Exact, Approximative, Robust and Certifying Algorithms on Particular Graph Classes

Organizers

Andreas Brandstädt (Universität Rostock, DE)
Klaus Jansen (Universität Kiel, DE)
Dieter Kratsch (University of Metz, FR)
Jeremy P. Spinrad (Vanderbilt University, US)

For support, please contact

Dagstuhl Service Team

Documents

Dagstuhl Seminar Proceedings DROPS
List of Participants

Summary

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.

Dagstuhl Seminar Series

Classification

  • Data Structures / Algorithms / Complexity

Keywords

  • Exact algorithms for NP-hard graph problems
  • Approximation algorithms for graph problems
  • Robust graph algorithms
  • Verified problem solving

Documentation

In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.

 

Download overview leaflet (PDF).

Publications

Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.

NSF young researcher support