Henning Bruhn-Fujimoto und Laura Gellert

Bei einer Vielzahl von Optimierungsproblemen stellt sich heraus, dass sie zwar aus theoretischer Sicht als schwer gelten müssten, in der Praxis jedoch effizient lösbar sind. Oftmals liegt dies an der eher speziellen Struktur der Eingaben, die in der Praxis auftreten. Zum Beispiel mögen diese Eingaben eher "dünn" sein, in dem Sinne, dass es eher wenige Abhängigkeiten innerhalb der Daten gibt.

In diesem Seminar wird eine Technik betrachtet, die eine eventuelle "Dünnheit" der Eingaben auf systematische Weise ausnutzt, um das gegebene Optimierungsproblem mittels dynamischer Programmierung zu lösen. Ein zentrales Maß für Dünnheit ist dabei die Baumweite. Desweiteren werden wir einen erstaunlichen Zusammenhang zur Logik beleuchten (Courcelle's theorem, monadic second order logic).


Voraussetzungen: Optimierung und/oder Graphentheorie nützlich, jedoch nicht zwingend erforderlich.

Provisorischer Zeitpunkt: dienstags 10h-12h (bei Terminüberschneidungen werden wir individuelle Lösungen finden)

Themen

1. Einführung (28. April, E60 HeHo 18, Henning Bruhn & Laura Gellert)

2. Definition von Baumzerlegungen und Baumweite (5. Mai, E60 HeHo 18, Fabrice Bacquele)
   Literatur

   • Graph Theory, Reinhard Diestel, Kapitel 10.3

   • A partial k-arboretum of graphs with bounded treewidth, Hans L. Bodlaender

3. Dynamische Programmierung in Bäumen und series-parallel graphs (19. Mai, E60 HeHo 18, Jonas Klesel)
   Algorithmen für Max Independent Set, evtl. Domination
   Literatur

   • Combinatorial Optimization on Graphs of Bounded Treewidth, Hans L. Bodlaender und Koster, Abschnitte 1 und 2

   • A linear algorithm for the domination number of a tree, E. Cockayne, S. Goodman und S. Hedetniemi

4. Dynamische Programmierung bei beschränkter Baumweite (26. Mai, E60 HeHo 18, Miriam Eicher-Abel)
   Algorithmen für Max Independent Set und Färbung
   Literatur

   • Combinatorial Optimization on Graphs of Bounded Treewidth, Hans L. Bodlaender und Koster, Abschnitt 3

5. Approximation von Wegbreite (2. Juni, E18 HeHo 22, Axel Dieing)
   Literatur

   • A Simple Linear-Time Algorithm for Finding Path-Decompositions of Small Width, Kevin Cattell, Michael J. Dinneen und Michael R. Fellows

6. Monadic Second Order Logic und Courcelles Satz (9. Juni, E60 HeHo 18, Christian Meyer)
   Definition MSO, Darstellung von Optimierungsproblemen in MSO, Bedeutung von Courcelles Satz
   Literatur

   • Invitation to Fixed-Parameter Algorithms, Niedermeier, Kapitel 10.6 & 10.8

7. Clique width, MSO1 und Courcelles Satz (16. Juni, E18 HeHo 22, Dragan Ströbele)
   Definition clique width, MSO1 vs MSO2, Anwendung für Co-Graphen
   Literatur

   • Width parameters beyond tree-width and their applications, Hlineny et al, Abschnitt 4

   • On the complexity of the maximum cut problem, Hans L. Bodlaender and Jansen, Abschnitt 5.1 (MaxCut in Co-Graphen) 

8. Model-Checking auf gelabelten Bäumen und Skizze des Beweises von Courcelles Satz (23. Juni, N25/2101)
   Reduktion des Ursprungsproblems auf das Model-Checking-Problem für MSO auf gelabelten Bäumen, Einführung in das Model-Checking auf Bäumen
   Literatur

   • Parameterized Complexity Theory, Flum and Grohe, Kapitel 10.2 & 11.4