Effizientere Algorithmen für Dekompositions-Parameter

Die grundlegende Idee, einen Graphen so in Teile zu zerlegen, dass die einzel- nen Teile sowohl intern als auch untereinander gewisse nutzliche Eigenschaften erfullen erlaubt auf naturliche Art und Weise die Anwendung zahlreicher all- gemein bekannter algorithmischer Ansatze, wie zum Beispiel dynamische Pro- grammierung oder divide&conquer-artige Methoden. Um diese abstrakte Heran- gehensweise systematisch zu betrachten, kann man sogenannte Dekompositions- Parameter definieren. Diese dienen als konkrete Messwerte dafur, wie schwierig es ist, einen Graph so zu zerlegen, dass die gewunschten gunstigen Eigenschaften dieser Zerlegung gewahrleistet sind. Die Vielzahl aller Algorithmen, die ein Graphproblem mit Hilfe der Struk- tur, die durch Dekompositions-Parameter impliziert wird, losen, funktioniert in zwei Schritten: Zunachst wird eine Zerlegung, die dem Dekompositions- Parameter entspricht berechnet, und danach wird diese Zerlegung benutzt, um das eigentliche Problem zu losen. Dieses Projekt zielt auf die Untersuchung zweier Problemstellungen ab, die wir als zentral ansehen, um ein genaues Verstandnis der Komplexitat solcher Al- gorithmen zu gewinnen. Dafur nutzen wir das relative junge, aber schon ex- trem erkenntnisbringende, Paradigma der detailierten oder feinkornigen param- eterisierten Komplexitatstheorie (fine-grained parameterised complexity theory). Bisher konzentrierte sich die Analyse der feinkornigen parameterisierten Kom- plexitat von klassischen Graphproblemen vornehmlich auf den zweiten oben beschriebenen Schritt. Unser erstes Ziel ist es daher, den ersten Schritt fur eine Reihe wichtiger Dekompositions-Parameter zu analysieren und die vergleich- sweise großen Lucken unserem Verstandnis uber die Komplexitat der Berech- nung ihrer entsprechenden Zerlegungen zu schließen. Unser zweites Ziel ist es, eine problemunspezifische Theorie zu entwickeln, um die allgemeine Starke und Grenzen einiger erfolgreicher dekompositionsbasierter algorithmischer Tech- niken zu verstehen, die bisher auf dem Gebiet der feinkornigen parametrisierten Komplexitat entwickelt wurden.