Parametrisierter Algorithmus

Die parametrisierte Algorithmik ist ein relativ junges Teilgebiet der theoretischen Informatik, in dem genauer untersucht wird, welche Instanzen von NP-vollständigen Problemen effizient zu lösen sind. Dabei wird untersucht, von welchen Faktoren (Parametern) die Laufzeit der Algorithmen im Wesentlichen abhängt. Zum Beispiel sind viele Graphen-Probleme schnell lösbar für Graphen mit kleiner Baumweite.

Formal ist ein Problem parametrisierbar (auch: fixed parameter tractable oder FPT), wenn ein Algorithmus existiert, der es mit einer Laufzeit aus $O(f(k)\cdot p(n))$ löst, wobei f eine berechenbare Funktion, k der Parameter, p ein beliebiges Polynom und n die Eingabelänge (z. B. bei Graphenproblemen die Anzahl der Knoten) ist.

Man beachte, dass ein Problem mit unterschiedlichen Parametern sowohl FPT, als auch nicht-FPT sein kann. Zum Beispiel ist das Cliquen-Problem nicht-FPT, wenn der Parameter die Größe einer maximalen Clique ist, aber FPT, wenn der Parameter die Baumweite oder der Maximalgrad ist. Man sagt auch, dass ein Problem parametrisierbar in dem entsprechenden Parameter ist, z. B. "Das Cliquen-Problem ist parametrisierbar in der Baumweite". Anschaulich ist ein Parameter, in dem ein NP-vollständiges Problem parametrisierbar ist, eine Eigenschaft, die das exponentielle Wachstum der Laufzeiten verursacht, da diese Probleme schnell lösbar sind, bis auf Instanzen, bei denen dieser Parameter groß ist.

In der Praxis ist f oft eine unangenehme Funktion wie k^k, man geht im Allgemeinen aber davon aus, dass k sehr klein ist (weil dies bei Instanzen, die in der Praxis vorkommen, häufig der Fall ist) und n groß werden kann. Parametrisierte Algorithmen sind in der Praxis (wo k klein ist) auch für n=50–100 praktikabel, wogegen z. B. gewöhnliche Brute-Force Algorithmen mit Laufzeiten wie O(2ⁿ) schon ab etwa n=20 nicht mehr praktikabel sind.

FPT-Reduktion

Ähnlich der Polynomialzeitreduktion, ist eine FPT-Reduktion eine Funktion, die selbst in FPT-Zeit berechenbar ist und eine Instanz eines Problems P₁ und den Parameter k₁ abbildet auf eine Instanz eines Problems P₂ und einen Parameter k₂ mit der Einschränkung $k_2\le k_1$. Man schreibt dann $P_1 \preceq_{FPT} P_2$.

Dies ist eine Einschränkung gegenüber Polynomialzeitreduktionen, weil sich bei diesen die Größe der Lösung beliebig verändern kann. So entspricht z. B. bei der Polynomialzeitreduktion des Independent Set Problems auf das Knotenüberdeckungsproblem die Größe der minimalen Knotenüberdeckung der Differenz zwischen der Anzahl der Knoten und der Größe des maximalen Independent Set. Hier ist also $k_2=n-k_1\not\le k_1$, also handelt es sich um eine i. A. unerlaubte Veränderung der Lösungsgröße, wodurch es sich hierbei nicht um eine FPT-Reduktion handelt. Tatsächlich stellt sich heraus, dass das Independent Set Problem W[1]-Hart ist, während das Knotenüberdeckungsproblem FPT ist, d. h. dass keine FPT-Reduktion von Independent Set auf das Knotenüberdeckungsproblem existiert, sofern $P \not= NP$ ist.

Aufgrund dieser Einschränkung gegenüber Polynomialzeitreduktionen liefert die FPT-Reduktion eine feinere Abstufung der Komplexitätsklasse NP und ermöglicht genauere Aussagen über die Komplexität von NP-Vollständigen Problemen.

So, wie aus $L \preceq_p L^\prime$ und $L^\prime\in P$ folgt, dass $L\in P$ ist, folgt aus $L \preceq_{FPT} L^\prime$ und $L^\prime\in FPT$, dass $L\in FPT$ ist. Umgekehrt folgt daraus, dass $L \preceq_{FPT} L^\prime$ und L W[t]-Hart ist, dass $L^\prime$ W[t]-Hart ist, so wie aus $L \preceq_p L^\prime$ und NP-Härte von L die NP-Härte von $L^\prime$ folgt.

Beschränkte Berechnungsbäume

Eine häufig benutzte Methode sind Berechnungsbäume, deren Höhe und Verzweigung durch Funktionen in k beschränkt sind. Die Verzweigung kann man häufig sogar durch Konstanten beschränken. Einen solchen Algorithmus kann man z. B. für das Knotenüberdeckungs-Problem benutzen, wobei der Parameter k die Größe einer minimalen Knotenüberdeckung ist.

Eine Methode wäre hier, eine beliebige, noch nicht überdeckte Kante e zu wählen und über die beiden zu e inzidenten Knoten zu verzweigen (in den beiden Zweigen des Berechnungsbaums wird je einer der Knoten in die Knotenüberdeckung aufgenommen). Die Verzweigung ist also 2 und da man maximal k Knoten wählt, ist die Höhe des Berechnungsbaums durch k beschränkt. Die Wahl einer noch nicht überdeckten Kante und die Aufnahme eines Knotens in die Knotenüberdeckung sind je in O(n) möglich, womit die Laufzeit insgesamt aus $O(2^k\cdot n)$ ist.

Problemkern-Reduktion

Ein entscheidbares Problem ist genau dann fixed parameter tractable, wenn dafür eine Problemkern-Reduktion existiert, die in Polynomialzeit berechenbar ist und die eine Instanz mit Parameter k reduziert auf eine Instanz, deren Größe durch eine Funktion f(k) beschränkt ist. Den Problemkern kann man dann mit einem Algorithmus lösen, der beliebige, endliche Laufzeit h hat. Damit erhält man insgesamt eine Laufzeit von h(g(k)), was zusammen mit der Polynomialzeit für die Reduktion immer noch eine FPT-Zeitbeschränkung liefert.

Diese Methode lässt sich z. B. auf das Knotenüberdeckungsproblem anwenden: Wenn ein Knoten einen größeren Grad als k hat, muss er in einer minimalen Knotenüberdeckung enthalten sein, denn wenn ein Knoten v nicht enthalten ist, müssen alle seine Nachbarn enthalten sein (da alle zu v inzidenten Kanten überdeckt werden müssen), was aber mehr als k Knoten wären, obwohl k als Größe einer minimalen Knotenüberdeckung definiert war.

Nachdem auf diese Weise Knoten ausgewählt wurden, die definitiv in einer minimalen Knotenüberdeckung enthalten sein müssen, können noch maximal k² + k Knoten übrig sein (k Knoten für die Knotenüberdeckung und jeweils maximal k Nachbarn), aus denen man in $2^k\cdot poly(n)$ Schritten eine Knotenüberdeckung auswählen kann.

Die Größe der Problemkerne liefert eine noch feinere Abstufung der Komplexitätsklasse FPT. So ist zum Beispiel das Knotenüberdeckungsproblem leichter als das Min-Multicut Problem auf Bäumen, obwohl beide FPT sind, weil der Problemkern einer Instanz des Knotenüberdeckungsproblems (nach Nemhauser und Trotter) höchstens Größe 2k hat, wogegen die beste bekannte Problemkernreduktion für Min-Multicut auf Bäumen Problemkerne liefert, die höchstens Größe k⁶ haben.

Interleaving

Die Interleaving Methode ist, vor jedem Rekursionsaufruf eine Problemkern-Reduktion durchzuführen. Im Allgemeinen wird die Laufzeit dadurch stark reduziert, von $O(s(n,k)\cdot t(n))$ auf O(s(n,k) + t(n) + r(n)), wobei s(n,k) die Anzahl der Knoten im Berechnungsbaum ist, t(n) die Laufzeit der Expansion eines Knotens im Berechnungsbaum (die Generierung der Nachfolger) und r(n) die Laufzeit der Problemkernreduktion ist.

Interleaving ist vor allem in Kombination mit Memoisation eine starke Methode zur Beschleunigung von Programmen für NP-Harte Probleme. Dies liegt daran, dass die Instanzen, die weiter unten im Berechnungsbaum auftreten, kleine Parameter haben, weswegen die Problemkerne klein sind und sich deshalb mit hoher Wahrscheinlichkeit oft wiederholen, wodurch die Memoisation viele Teilbäume des Berechnungsbaums abschneiden kann.

Color-Coding

Eine weitere Methode ist das Color-Coding, bei dem man die n Objekte in der Probleminstanz mit k Farben „färbt“. Wenn eine Lösung aus k Objekten aus der Instanz besteht, kann sie häufig schnell gefunden werden, wenn diese k Objekte unterschiedlich gefärbt sind. Man sagt dann, dass die Lösung farbenfroh (engl. colorful) ist. Da es perfekte Hash-Funktionen gibt, müssen höchstens $O(c^k\cdot \log(n))$ verschiedene Färbungen probiert werden, bis eine Lösung farbenfroh ist, wobei c eine Konstante ist.

Mit dieser Methode ist z. B. die Suche in einem Graphen nach einem Weg der Länge k parametrisierbar. Sind die Knoten auf einem Weg der Länge k unterschiedlich gefärbt, dann können die Farbklassen auf k! Arten angeordnet werden, alle Kanten entfernt werden, die zwischen nicht-benachbarten Farbklassen verlaufen, woraufhin z. B. mit dem Algorithmus von Floyd und Warshall in O(n³) geprüft werden kann, ob es noch einen Weg von einem Knoten der ersten Farbklasse zu einem Knoten der letzten Farbklasse gibt (falls es einen gibt, hat er mindestens Länge k). Die Laufzeit dieses Algorithmus ist in $O(c^k\cdot k! \cdot n^3 \cdot \log(n))$, also ist es ein FPT Algorithmus.

Courcelles Theorem

Courcelles Theorem besagt, dass jedes Graphenproblem, welches durch eine erweiterte MS₂-logische Formel beschrieben werden kann, parametrisierbar ist mit der Baumweite als Parameter. Eine erweiterte MS₂-logische Formel ist dabei eine logische Formel mit Existenz- und Allquantor, die Mengen von Knoten oder Kanten quantifizieren können, erweitert um einen min und einen max Quantor.

Formeln aus erweiterter MS₂-Logik für folgende Probleme auf einem Graphen G=(V,E) sind z. B.:

1. Minimale Knotenüberdeckung: $\min U\subseteq V: \forall e \in E: \exists v \in U: \operatorname{inc}(v,e)$
2. Minimale dominierende Knotenmenge: $\min U\subseteq V: \forall v \in V: (v \in U \vee \exists v' \in U: \operatorname{adj}(v,v'))$
3. Maximale Clique: $\max U\subseteq V: \forall v,v' \in U: \operatorname{adj}(v,v')$

Für Klassen von Graphen, die dadurch charakterisiert sind, dass ein planarer Graph als Minor verboten ist, sind alle diese Probleme in Polynomialzeit berechenbar, weil diese Graphklassen je eine konstante obere Schranke für die Baumweite haben. Dies betrifft zum Beispiel die Klasse der triangulierten Graphen und die Klasse der Wälder.

Literatur

• Rod Downey, M. Fellows: Parameterized complexity. Springer 1999, ISBN 0-387-94883-X

• Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer 2006, ISBN 978-3-540-29952-3

• Rolf Niedermeier: Invitation to Fixed-Parameter Algorithms. Oxford University Press 2006, ISBN 0-19-856607-7

Weblinks

• Wiki über Parametrisierte Komplexitätstheorie
• Compendium of Parameterized Problems