Parametrisierte Algorithmen

Inhalt

In der Algorithmentheorie wird der Aufwand eines Algorithmus üblicherweise (asymptotisch) im Verhältnis zur Größe seiner Eingaben ausgedrückt. Bei Graphenalgorithmen oft auch in der Anzahl der Knoten des Graphen. Für viele algorithmische Probleme sind in dieser Betrachtungsweise nur Algorithmen mit exponentiellem Zeitaufwand bekannt.

Ein Beispiel hierfür ist das Vertex Cover Problem: Gegeben ein Graph G und eine Zahl k, fragt es, ob es eine Menge M von k Knoten gibt, so dass jede Kante des Graphen einen Knoten in M hat. Interessanterweise gibt es jedoch einen sehr simplen Algorithmus, dessen Aufwand O(n 2^k) ist, wobei n die Anzahl der Knoten des Eingabegraphen ist. Intuitiv ist der Aufwand dieses Algorithmus also "nur" schlecht in k, aber nicht in n. Anders gesagt: für Eingaben mit "kleinem" k lässt sich das Problem effizient lösen.

Solche Parametrisierungen gibt es auch für eine Reihe anderer algorithmischer Probleme. Entsprechende Algorithmen dieser Art wollen wir in dem Proseminar betrachten.

Die Vortragsthemen basieren zum Teil auf dem Buch Invitation to Fixed-Parameter Algorithms von Rolf Niedermeier, zum Teil auf dem Buch Fundamentals of Parameterized Complexity von Rodney G. Downey und Michael R. Fellows. Die dem Buch von Herrn Niedermeier zugrunde liegende Habilitationsschrift finden Sie hier: http://theinf1.informatik.uni-jena.de/~niedermr/publications.html.

Darüber können den Vorträgen weitere Bücher und Originalarbeiten zugrunde liegen.