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 von ${\displaystyle 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 und Kanten) ist.

Man beachte, dass ein Problem mit unterschiedlichen Parametern sowohl FPT, als auch nicht-FPT sein kann. Zum Beispiel ist das Cliquenproblem 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 ${\displaystyle 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 ${\displaystyle O(2^{n})}$ schon ab etwa n=20 nicht mehr praktikabel sind.

Das Gebiet wurde von Rod Downey und Michael Fellows in den 1990er Jahren begründet.

FPT-Reduktion

Ähnlich der Polynomialzeitreduktion, ist eine FPT-Reduktion eine Funktion, die selbst in FPT-Zeit berechenbar ist und eine Instanz ${\displaystyle I_{1}}$ eines Problems ${\displaystyle P_{1}}$ und den Parameter ${\displaystyle k_{1}}$ abbildet auf eine Instanz ${\displaystyle I_{2}}$ eines Problems ${\displaystyle P_{2}}$ und einen Parameter ${\displaystyle k_{2}}$ mit der Einschränkung, dass ${\displaystyle I_{1}}$ eine positive Instanz für ${\displaystyle P_{1}}$ ist genau dann wenn ${\displaystyle I_{2}}$ eine positive Instanz für ${\displaystyle P_{2}}$ ist, und ${\displaystyle k_{2}\leq f(k_{1})}$ wobei ${\displaystyle f\colon \mathbb {N} \to \mathbb {N} }$ eine berechenbare Funktion ist. Man schreibt dann ${\displaystyle P_{1}\preceq _{FPT}P_{2}}$.

Dies ist eine Einschränkung gegenüber Polynomialzeitreduktionen, weil sich bei diesen Parameter beliebig verändern können. So entspricht z. B. bei der Polynomialzeitreduktion des Independent Set Problems auf das Knotenüberdeckungsproblem der Parameter ${\displaystyle k_{2}}$ "Größe der minimalen Knotenüberdeckung" der Differenz zwischen der Anzahl ${\displaystyle n}$ der Knoten und der Größe, ${\displaystyle k_{1}}$, des maximalen Independent Set. Hier kann also im Allgemeinen keine Funktion ${\displaystyle f}$ existieren, sodass ${\displaystyle k_{2}=n-k_{1}\leq f(k_{1})}$, also handelt es sich um eine i. A. unerlaubte Veränderung der Parameter, wodurch es sich hierbei nicht um eine FPT-Reduktion in Hinsicht auf die Parameter ${\displaystyle k_{1}}$ und ${\displaystyle k_{2}}$ handelt. Tatsächlich stellt sich heraus, dass das Independent Set Problem W[1]-schwierig ist, während das Knotenüberdeckungsproblem FPT ist, d. h., dass keine FPT-Reduktion von Independent Set auf das Knotenüberdeckungsproblem existiert, sofern ${\displaystyle 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 ${\displaystyle L\preceq _{p}L^{\prime }}$ und ${\displaystyle L^{\prime }\in P}$ folgt, dass ${\displaystyle L\in P}$ ist, folgt aus ${\displaystyle L\preceq _{FPT}L^{\prime }}$ und ${\displaystyle L^{\prime }\in FPT}$, dass ${\displaystyle L\in FPT}$ ist. Umgekehrt folgt daraus, dass ${\displaystyle L\preceq _{FPT}L^{\prime }}$ und ${\displaystyle L}$ W[t]-schwierig ist, dass ${\displaystyle L^{\prime }}$ W[t]-schwierig ist, so wie aus ${\displaystyle L\preceq _{p}L^{\prime }}$ und der NP-Schwere von ${\displaystyle L}$ die NP-Schwere von ${\displaystyle 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überdeckungsproblem 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 ${\displaystyle O(n)}$ möglich, womit die Laufzeit insgesamt aus ${\displaystyle 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(f(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 ${\displaystyle k^{2}+k}$ Knoten übrig sein (k Knoten für die Knotenüberdeckung und jeweils maximal k Nachbarn), aus denen man in ${\displaystyle 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 ${\displaystyle k^{6}}$ haben.

Interleaving

Die Interleaving Methode ist, vor jedem Rekursionsaufruf eine Problemkern-Reduktion durchzuführen. Im Allgemeinen wird die Laufzeit dadurch stark reduziert, von ${\displaystyle O(s(n,k)\cdot t(n))}$ auf ${\displaystyle O(s(n,k)+t(n)+r(n))}$, wobei ${\displaystyle s(n,k)}$ die Anzahl der Knoten im Berechnungsbaum ist, ${\displaystyle t(n)}$ die Laufzeit der Expansion eines Knotens im Berechnungsbaum (die Generierung der Nachfolger) und ${\displaystyle 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-schwierige 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 ${\displaystyle 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 ${\displaystyle O(n^{3})}$ 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 ${\displaystyle 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 ${\displaystyle \mathrm {MS} _{2}}$-logische Formel beschrieben werden kann, parametrisierbar ist mit der Baumweite als Parameter. Eine erweiterte ${\displaystyle \mathrm {MS} _{2}}$-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 ${\displaystyle \mathrm {MS} _{2}}$-Logik für folgende Probleme auf einem Graphen G=(V,E) sind z. B.:

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

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.
• Marek Cygan, Fedir V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh: Parameterized Algorithms. Springer International Publishing, 2016, ISBN 978-3-319-21274-6, doi:10.1007/978-3-319-21275-3. 

Weblinks

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