Seminar Algorithmen in der Graphentheorie

Dieses Seminar ist eine Ergänzung zu den Algorithmen Vorlesungen. Wir betrachten  fixed-parameter Algorithmen.

Für kombinatorisch schwierige Probleme (NP-harte Probleme) gibt es keine effizienten Algorithmen. Vereinfacht man ein derartiges Problem auf geeignete Weise, so kann man effiziente Algorithmen entwickeln und analysieren. Eine Möglichkeit besteht darin, das Problem zu parametrisieren. Die Eingabe besteht aus der Probleminstant und einer Zahl, dem Parameter k. Im Allgemeinen sind wir an Algorithmen interessiert, die in f(k)nO(1) Schritten eine Lösung finden.

Betrachten wir zum Beispiel das Vertex Cover Problem. Als Parameter nehmen wir die Größe des Vertex Covers:
Gegeben: (G,k) ein Graph und eine Zahl k.
Gesucht: Gibt es im Graph G eine Menge S mit höchstens k Knoten, sodass jede Kante einen Endpunkt in S hat.
Mit erschöpfender Suche bekommt man eine Lösung in 2O(k)nO(1) Schritten.

Überblick:

• Fixed-Parameter Algorithmen
• Dominating Set,  Vertex Cover, Independent Set Problem
• Betrachtung von diesen Problemen auf eingeschränkten Graphklassen, z.B. Planare Graphen
• Techniken, wie Problemkern-Reduktion, Baumzerlegungen, Dynamisches Programmieren, tiefenbeschränkte Suchbäume
• Subgraphisomorphie- bzw. Graphenisomorphieproblem

Literatur:

• R. Niedermeier: Invitation to Fixed-Parameter Algorithms. Oxford University Press, 2006.