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


Dagstuhl Seminar 07211

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

( May 20 – May 25, 2007 )

(Click in the middle of the image to enlarge)

Permalink
Please use the following short url to reference this page: https://www.dagstuhl.de/07211

Organizers



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.


Participants
  • Anne Berry (University Blaise Pascal - Aubiere, FR)
  • Andreas Brandstädt (Universität Rostock, DE) [dblp]
  • Victor Chepoi (Aix-Marseille University, FR)
  • Derek G. Corneil (University of Toronto, CA) [dblp]
  • Celina de Figueiredo (University of Rio de Janeiro, BR)
  • Feodor F. Dragan (Kent State University, US)
  • Jack E. Edmonds (University of Waterloo, CA)
  • Elaine M. Eschen (West Virginia University - Morgantown, US)
  • Fedor V. Fomin (University of Bergen, NO) [dblp]
  • Serge Gaspers (University of Bergen, NO) [dblp]
  • Michel Habib (University of Paris VII, FR)
  • Pinar Heggernes (University of Bergen, NO) [dblp]
  • Chinh T. Hoàng (Wilfrid Laurier University, CA) [dblp]
  • Christian Hundt (Universität Rostock, DE)
  • Klaus Jansen (Universität Kiel, DE) [dblp]
  • Tilo Klembt (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]
  • Mathieu Liedloff (Université Paul Verlaine - Metz, FR) [dblp]
  • Marina Lipshteyn (Haifa University, IL)
  • Ross McConnell (Colorado State University, US)
  • Rolf Niedermeier (Universität Jena, DE) [dblp]
  • Michaël Rao (University of Paris VII, FR)
  • Dieter B. Rautenbach (TU Illmenau, DE) [dblp]
  • Peter Rossmanith (RWTH Aachen, DE) [dblp]
  • Ingo Schiermeyer (TU Bergakademie Freiberg, DE) [dblp]
  • Ulrich Michael Schwarz (Christian-Albrecht-Universität zu Kiel, DE)
  • Jeremy P. Spinrad (Vanderbilt University, US)
  • R. Sritharan (University of Dayton, US)
  • Jayme L. Szwarcfiter (Federal University - Rio de Janeiro, BR)
  • Ioan Todinca (University of Orleans, FR) [dblp]
  • Peter Wagner (Universität Rostock, 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 11182: Exploiting graph structure to cope with hard problems (2011-05-01 - 2011-05-06) (Details)
  • Dagstuhl Seminar 14071: Graph Modification Problems (2014-02-09 - 2014-02-14) (Details)

Classification
  • data structures / algorithms / complexity

Keywords
  • exact algorithms for NP-hard graph problems
  • approximation algorithms for graph problems
  • robust graph algorithms
  • verified problem solving