Parametrisierte Algorithmen Rolf Niedermeier in Zusammenarbeit mit Jochen Alber Wilhelm-Schickard-Institut für Informatik, Universität Tübingen, Sand 13, D-72076 Tübingen nieder mr ©Informatik. uni-1 uebingen. de 'Skript zu einer zweistündigen Vorlesung im Sommersemester 1999 für den Bereich „Theoretische Informatik" an der Universität Tübingen. Das Skript ist erhältlich über http://www-fs.informatik.uni-tuebingen.de/~niedermr/lehre/ Version vom 14. Februar 2003. 1 Inhaltsverzeichnis 0 Vorwort 4 1 Ein einführendes Beispiel 5 2 Standortbestimmung 8 2.1 Ansätze zur Behandlung komplexitätstheoretisch harter Probleme ............................... 8 2.1.1 Average Case- statt Worst Case-Analyse........ 8 2.1.2 Approximation...................... 8 2.1.3 Randomisierte Algorithmen............... 9 2.1.4 Heuristische Verfahren.................. 10 2.1.5 Neue Berechnungsmodelle................ 10 2.1.6 Parametrisierte Algorithmen .............. 10 2.2 Aspekte der Parametrisierung.................. 11 2.2.1 Laufzeit-Argumente................... 11 2.2.2 Parametrisierte Algorithmen — eine Normalität? ... 13 3 Grundlegende Definitionen 17 4 Grundlegende Methoden 21 4.1 Reduktion auf den Problemkern................. 21 4.2 Tiefenbeschränkte Suchbäume.................. 30 4.3 Verflechtung von Problemkernreduktion und Suchbaummethode ............................... 36 4.4 Farbkodierungen und Hashing.................. 38 4.5 Beschränkte Baumweiten .................... 43 4.5.1 Dynamisches Programmieren bei gegebener Baumzerlegung ........................... 43 4.5.2 Konstruktion von Baumzerlegungen.......... 47 4.6 Graphminoren .......................... 50 2 5 Bezüge zur Approximation 53 6 Parametrisierte Komplexitätstheorie 57 6.1 Parametrisierte Reduktion.................... 57 6.2 Parametrisierte Komplexitätsklassen.............. 60 6.3 Vollständige Probleme und die W-Hierarchie ......... 64 6.4 Strukturelle Ergebnisse...................... 69 7 Blick zurück und nach vorn 71 Literaturverzeichnis 72 Indexregister 74 3 0 Vorwort Viele Probleme von großer praktischer Bedeutung erweisen sich als NP-h&it, das heißt, für sie sind keine effizienten Algorithmen bekannt. In der Praxis wird zu ihrer Lösung daher meist auf heuristische Verfahren zurückgegriffen, die zwar oftmals ausreichend gute Laufzeiten bzw. Lösungen liefern, aber leider meist schwer durchschaubar sind und keine garantierten Aussagen über ihre Leistungsgüte erlauben. Ein möglicher Ausweg aus dem „Dilemma der iVP-Härte" kann in der Betrachtung von „parametrisierter Komplexität" bestehen: Bei vielen iVP-harten Problemen läßt sich die scheinbar inhärente „kombinatorische Explosion" auf einen kleinen Teil der Eingabe, einen sogenannten Parameter beschränken. Dies führt zu dem Konzept der para-metrisierten Algorithmen, welche eine sinnvolle Alternative zu heuristischen Methoden darstellen können. In der Vorlesung werden die Möglichkeiten und Grenzen parametrisierter Algorithmen aufgezeigt. Das Schwergewicht der Vorlesung liegt auf grundlegenden Methoden zur Entwicklung effizienter, parametrisierter Algorithmen. Diese werden an wichtigen Beispielen erläutert. Abgerundet wird diese Einführung in die Welt der parametrisierten Algorithmen mit einer kurzen Darstellung einer parametri-sierten Komplexitätstheorie. Die Hauptquelle zu dieser Vorlesung ist die jüngst erschienene Monographie von Downey and Fellows [12]. Es werden aber noch einige andere Ubersichtsartikel [13, 20, 24] und Forschungspapiere herangezogen — die spezifischen Referenzen werden an den entsprechenden Textstellen gegeben und finden sich im Literaturverzeichnis am Ende des Skripts. Zuletzt sein noch darauf verwiesen, daß der englischsprachige Fachbegriff genauer „fixed parameter algorithm" lautet. Dieser wurde hier nur kurz mit „parametrisierter Algorithmus" übersetzt. Für diese Vorlesung setzen wir elementare Vorkenntnisse aus dem Grundstudium voraus. So nehmen wir Begriffe wie Laufzeit eines Algorithmus, Turingmaschine, O-Notation oder einfache graphentheoretische Notationen als bekannt an. Informationen zu diesen Themengebieten, welche eng mit den hier behandelten Sachverhalten in Verbindung stehen, finden sich z.B. in den Lehrbüchern [9, 18, 23]. 4 1 Ein einführendes Beispiel: Vertex Cover Als einführendes Beispiel stellen wir ein aus der Graphentheorie bekanntes Problem vor, das sog. Vertex Cover (deutsch: Knotenüberdeckungsproblem). Dieses Problem ist auch unter dem Namen Node Cover bekannt. Wir werden im Verlauf der Vorlesung mehrfach auf dieses Beispiel zurückgreifen. Beispiel 1.1. Gegeben: Ein ungerichteter Graph G = (V,E), wobei wie üblich V die Knotenmenge und E die Kantenmenge bezeichnet, und eine natürliche Zahl k. Frage: Gibt es eine Teilmenge C c V der Mächtigkeit \C\ < k derart, daß jede Kante aus E mindestens einen Endpunkt in C hat? In Abbildung 1 sind zwei Vertex Cover der Größe k = 4 für einen vorgegebenen ungerichteten Graphen dargestellt. Man erkennt, daß eine solche Knotenüberdeckung zu festem k im allgemeinen nicht eindeutig zu sein braucht. Für den gegebenen Graphen überprüft man leicht, daß kein Vertex Cover der Größe 3 existiert. Abbildung 1: Vertex Cover für einen ungerichteten Graphen Wir halten einige wichtige Anmerkungen zu Vertex Cover fest: • Vertex Cover ist NP-vollständig. Historisch gesehen, ist Vertex Cover sogar eines der allerersten als iVP-vollständig nachgewiesenen Probleme (vgl. [15]). • Vertex Cover ist relevant in der Praxis, z.B. in der algorithmischen Biologie zur Behandlung von sog. Konfliktgraphen1. 1 Siehe hierzu etwa das DARWIN-Projekt der ETH Zürich unter http://cbrg.inf.ethz.ch/VertexCover.html Vertex Cover 1: k = 4 Vertex Cover 2: k = 4 5 • Vielfach wird Vertex Cover also mit heuristischen Verfahren gelöst. Wenden wir uns nun der algorithmischen Seite des Problems zu. Zunächst stellen wir zwei verschiedene Polynomzeit-Approximationsalgorithmen für Vertex Cover vor. 1. Versuch: „Greedy"-Heuristik: starte mit C := 0; while (es gibt noch Kanten in G) do Nimm den Knoten mit größter Anzahl von Nachbarn, füge ihn zu C hinzu und lösche ihn zusammen mit seinen anliegenden Kanten aus G Hierbei handelt es sich um keinen guten Approximationsalgorithmus: Aufgabe 1.2. Konstruiere einen Graphen, der unter obigem Algorithmus eine Lösung C besitzt, welche Inn mal so groß ist, wie das Optimum {n = Anzahl der Knoten). 2. Versuch: "Trivialer Ansatz": starte mit C := 0; while (es gibt noch Kanten in G) do Nimm irgendeine Kante {u, v}, füge sowohl u als auch v zu C hinzu und lösche beide aus G zusammen mit den anliegenden Kanten Lemma 1.3. Obiger Algorithmus („Trivialer Ansatz") liefert ein Vertex Cover, welches schlimmstenfalls doppelt so groß ist wie das optimale Vertex Cover, (kurz: Obiger Algorithmus liefert eine Faktor-2-Approximation.) Beweis. Beobachtung: Nach Ablauf des Algorithmus enthält C genau ||C| Kanten aus G, von denen keine zwei einen gemeinsamen Knoten haben. Es gilt: Jedes Vertex Cover, insbesondere auch das optimale, muß mindestens einen Knoten von jeder dieser Kanten beinhalten. Mit obiger Beobachtung muß das Optimum also mindestens ||C| Knoten beinhalten, also liefert der vorgestellte Algorithmus eine Faktor-2-Approximation. □ Bemerkung 1.4. • Obiger Algorithmus ist im wesentlichen der beste bekannte Approximationsalgorithmus für Vertex Cover. Es geht lediglich asymptotisch besser: Nach einem Ergebnis von Monien/Specken-meyer [19] und Bar-Yehuda/Even [4] existiert eine Approximation mit Faktor (2 - . \ 2 log n I 6 • Nach einem Ergebnis von Hästad [16] kann es keinen besseren Approximationsalgorithmus als einen solchen mit Faktor 1.1666, es sei denn P = NP. Zuletzt geben wir einen einfachen, parametrisierten Algorithmus für Vertex Cover an: Tiefenbeschränkter Suchbaum: 1. Konstruiere einen vollständigen Binärbaum der Tiefe k. 2. Markiere den Wurzelknoten mit (G,0). 3. Die restlichen Baumknoten werden rekursiv wie folgt markiert: Sei (H, S) ein markierter Baumknoten mit zwei unmarkierten Kindern. Wähle irgendeine Kante {u, v} aus der Kantenmenge von H. (a) Markiere das linke Kind mit (H — u, S U {u})-2 (b) Markiere das rechte Kind mit {H — v, S U {v}). 4. if Es gibt einen Baumknoten mit Markierung (q^^, S') then S' ist ein Vertex Cover der Größe < k eise Es existiert kein Vertex Cover der Größe < k in G. Die Korrektheit des Algorithmus ist sofort einsichtig. Beachte hierzu, daß — wie wir dies schon bei unserem 2. Approximationsalgorithmus festgestellt hatten — von jeder Kante in G mindestens ein Endpunkt im Vertex Cover liegen muß. Dieser Algorithmus hat die Laufzeit 0(2k-\G\), wo 2k der Baumgröße entspricht und pro Baumknoten der Graph im wesentlichen einmal durchlaufen werden muß. Der Faktor |G| bezeichne dabei die Graphgröße. Zentrale Beobachtung: Ist k „klein" im Vergleich zur Eingabegröße n, so ist obiger Algorithmus „effizient". Bemerkung 1.5. • Oftmals ist die Annahme eines im Vergleich zur Eingabegröße n kleinen Parameters k sehr natürlich, so z.B. bei der Vertex Cover Anwendung in der algorithmischen Biologie. • Für k = O(logn) liefert obige Suchbaummethode einen Polynomzeitalgorithmus, ist also Vertex Cover in der Komplexitätsklasse P. 2Unter der Kurzschreibweise H — u verstehen wir das Löschen des Knoten u und aller anliegenden Kanten aus H. 7 2 Standortbestimmung In vielen Anwendungsfällen hat es den Anschein, die Welt sei voll von „hartnäckigen Problemen" (iVP-harten Problemen). Ungeachtet ihrer Schwierigkeit müssen diese Probleme in der Praxis jedoch gelöst werden. Als Beispiel hatten wir bereits das Problem Vertex Cover kennengelernt, für welches es wegen seiner NP-Vollständigkeit im allgemeinen (worst case) wohl keinen effizienten Algorithmus geben kann. Wir wollen in diesem Abschnitt der Frage nachgehen, welche Auswege man finden kann, um das oben angeführte Dilemma zu umgehen. 2.1 Ansätze zur Behandlung komplexitätstheoretisch harter Probleme In diesem Abschnitt stellen wir die gegenwärtig bekannten Ansätze zur Behandlung kombinatorisch schwieriger Probleme vor und geben eine kurze, vergleichende Bewertung. 2.1.1 Average Case- statt Worst Case-Analyse Cantus firmus: „In der Praxis interessieren oft die durchschnittlichen Laufzeiten mehr als die schlimmst möglich auftretenden." Die Laufzeit eines Algorithmus soll also in irgendeiner Form über alle Ein-gabeveteilungen „gemittelt" werden. Probleme: • Was ist eine realistische Eingabeverteilung? • Selbst für einfachste Algorithmen und Verteilungen ist die Average Case-Analyse in der Regel mathematisch sehr schwierig. In der Literatur sind — mit einigen wenigen Ausnahmen — für einen solchen Ansatz recht wenig Ergebnisse und Methoden bekannt. • Ein Problem kann auch im Average Case hart bleiben... 2.1.2 Approximation Cantus firmus: „Sei weniger anspruchsvoll und sei auch mit nicht-optimalen Lösungen zufrieden." 8 Dieser Ansatz gilt als der (zumindest von den Theoretikern) am meisten favorisierte Zugang. Dies spiegelt sich in einer sehr großen Anzahl von Veröffentlichungen wider. Probleme: • Viele der Probleme erweisen sich als hart zu approximieren: Im Fall von Vertex Cover hat der beste bekannte Approximationsalgorithmus Faktor 2 (vgl. Kapitel 1). Es gibt aber auch Probleme, die nur weitaus schlechtere Faktoren zulassen. Als Beispiel sei Clique genannt. Hier dabei ist V die Knotenmenge des Eingabegraphen. Als untere Schranke wurde bereits nachgewiesen, daß kein besserer Approximations-Faktor als |V^4~e für jedes e > 0 gefunden werden kann (vgl. [11]). • Der Ansatz macht nur Sinn bei Optimierungsproblemen, nicht aber bei „reinen" Entscheidungsproblemen wie das Erfüllbarkeitsproblem aussagenlogischer Formeln (Sat), etc. 2.1.3 Randomisierte Algorithmen Cantus firmus: „Vertraue auf den Zufall, sei auch mit Ergebnissen zufrieden, die nur mit hoher Wahrscheinlichkeit korrekt sind oder nur mit hoher Wahrscheinlichkeit in kurzer Laufzeit zu erzielen sind." Dieser Ansatz findet in vielen Bereichen Anwendungen: Kryptographie (Primzahltests), algorithmische Geometrie, Pattern Matching (Mustererkennung), etc. Randomisierte Algorithmen3 sind oftmals sehr einfach zu implementieren, meist gar deutlich einfacher als die entsprechenden deterministischen Algorithmen. Außerdem ist bereits eine Vielzahl von Techniken und Methoden gut bekannt. Probleme: • „Wahrscheinlich" taugt die Randomisierung nicht, um iVP-harte Probleme in Polynomzeit zu lösen. (Für Eingeweihte: Komplexitätstheoretisch vermutet man P = B P P.) • Viele randomisierte Algorithmen lassen sich zu deterministischen Algorithmen „derandomisieren". 3Man vergleiche hierzu das Vorlesungsskript zur gleichnamigen Vorlesung. Dieses kann bezogen werden unter: http://www-fs.informatik.uni-tuebingen.de/~niedermr ist ein Approximationsalgorithmus bekannt 9 2.1.4 Heuristische Verfahren Cantus firmus: „Die in der Praxis auftretenden Probleme sind meist nicht so hart wie sie sein könnten und in der Regel klappt's, diese effizient zu lösen — aber wir garantieren für nichts." Unter diesem Ansatz, den man als die Methode der Praktiker bezeichnen darf, verstehen wir Verfahren wie etwa: Simulated Annealing, Genetische Algorithmen, Neuronale Netze, Künstliche Intelligenz, Tabu Search, Branch & Bound, etc. Problem: In der Regel lassen sich keine „stichhaltigen", mathematisch beweisbaren Aussagen über die Leistung solcher Algorithmen treffen. Viele parametrisierte Algorithmen taugen auch als Heuristiken oder sind zumindest als Subroutinen von heuristischen Verfahren einsetzbar. Es ist denkbar, daß sich über parametrisierte Algorithmen sogar ein systematischer Zugang zur Entwicklung von heuristischen Verfahren ergibt. Dies ist ein neuer Forschungstrend. 2.1.5 Neue Berechnungsmodelle DNA-Computer: „Rechnen mit molekularer 'brüte force' ". Quantum-Computer: „Parallelisierung dank quantenmechanischer Effekte." Probleme: • Praktische Implementierung noch in weiter Ferne. • Es ist unklar, ob solche Ansätze allgemein anwendbar, oder nur auf spezielle Probleme zugeschnitten sind. 2.1.6 Parametrisierte Algorithmen Cantus firmus: „Nicht alle Formen von 'Härte' sind gleich geschaffen." Idee: Beschränke die bei iVP-harten Problemen scheinbar inhärente kombinatorische Explosion auf den Parameter. Der 0(2k ■ n)-Algorithmus für Vertex Cover zeigt, daß die exponentielle Explosion bezüglich dem Parameter k und nicht bezüglich der Eingabegröße n auftritt. Man kann sich diesen Sachverhalt durch das Bild in Abbildung 2 versinnbildlichen. Probleme werden wir im Rahmen der Vorlesung kennenlernen.... 10 Abbildung 2: Kombinatorische Explosion iVP-harter Probleme auf Parameter k beschränkt statt auf ganze Eingabegröße n = \X\ einwirkend. 2.2 Aspekte der Parametrisierung In diesem Abschnitt lernen wir einige grundlegende Prinzipien und Beobachtungen kennen, die die Betrachtung parametrisierter Komplexität motivieren. 2.2.1 Laufzeit-Argumente Wir geben einen kurzen Vergleich zwischen exponentiellen und polynomiel-len Laufzeiten. Unsere Angaben stützen sich auf Annahme einer Eingabegröße n = 50 und einen Rechner, welcher mit 108 Operationen pro Sekunde arbeitet. Polynomiell Exponentiell Komplexität Laufzeit Komplexität Laufzeit n2 25 /xsec 1.5n 6 min n3 1 min 2n 130 Tage n5 3 sec T 230 • 106 Jahre Leider sind für iVP-harte Probleme bestenfalls Algorithmen mit exponenti-eller Laufzeit bekannt. Im folgenden werden wir 3 parametrisierte Probleme (aus der Graphentheorie) kennenlernen und uns die Frage stellen, ob diese „effiziente" parametrisierte Algorithmen zulassen. Gegeben sei stets ein Graph G = (V, E) und ein Parameter k g N. Problem 1: Vertex Cover Gibt es ein S c V mit \S\ < k, so daß jede Kante aus E mindestens einen Endpunkt in S besitzt. 11 Problem 2: Independent Set Gibt es ein S c V mit \S\ > fc, so daß keine 2 Knoten in S in G benachbart sind. Problem 3: Dominating Set Gibt es ein S C.V mit \S\ < k, so daß jeder Knoten in V mindestens einen Nachbarn in S besitzt. Beispiele: siehe Abbildung 3. Vertex Cover k = 6. Independent Set k = 4. Dominating Set k = 3. Abbildung 3: Beispiele für Vertex Cover, Independent Set und Dominating Set. Möglichkeiten für die entsprechend gesuchten Mengen sind jeweils eingekreist. Der „Brüte-Force"-Ansatz zur Lösung aller 3 Probleme: „Probiere alle Teilmengen S der Größe k durch." Da es genau (^) solche Teilmengen gibt (wobei n = \V\), können wir mit geeigneten Datenstrukturen auf diese Weise einen Algorithmus mit Laufzeit 0(nk+1) angeben. Hier wurde (^) ~ 0(nk) verwendet. Wie wir gesehen haben (siehe Kapitel 1), können wir für Vertex Cover auch einen 0(2k ■ n)-Algorithmus angeben. Wir vergleichen die Laufzeiten des 0(nfc+1)-"Brute Force"-Algorithmus mit dem 0(2k -n)-Algorithmus für Vertex Cover, indem wir uns für verschiedene Werte von n und k den Quotienten n2un ansehen: n = 50 n=150 k-- =2 625 5625 k-- =5 390625 31640625 k-- =20 1.8 • 1026 2.1 • 1035 12 Bemerkung 2.1. Im Gegensatz zu Vertex Cover sind für Independent Set und Dominating Set im wesentlichen keine besseren Ansätze als oben genannte „Brüte-Force"-Verfahren bekannt. Fazit 2.2. Nicht alle „parametrisierten Probleme" besitzen effiziente para-metrisierte Algorithmen. Wir suchen also nach Algorithmen, die möglichst kleine, ausschließlich auf k beschränkte exponentielle Laufzeitkomponente haben. Für Vertex Cover klappt dies — wie bereits gesehen — sehr gut: Uns ist bereits ein 0(2k ■ n)-Algorithmus bekannt. Die Laufzeit läßt sich für dieses Problem sogar auf 0(1.292fc • n) reduzieren [22]4. Abschließend ein kleiner Vergleich von 2k und 1.292fc, durch Berechnung des Quotienten 1 ^g2fc ps 1.548fc für verschiedene Werte von k: k=2 ps 9 k=10 ps 80 k=20 ps 6240 k=40 ps 3.9-10 k=80 ps 1.5 • 10 Fazit 2.3. Selbst vermeintlich kleine Änderungen in der exponentiellen Basis eines parametrisierten Algorithmus können einen riesigen Effizienzgewinn bewirken. 2.2.2 Parametrisierte Algorithmen — eine Normalität? Parameter (beschränkter Größe) treten in natürlicher Weise in vielen Anwendungsgebieten auf, z.B.: VLSI-Entwurf: z.B. entspricht bei Problemen, die beim Layout in der Chip-Produktion auftreten, k etwa der beschränkten Anzahl von Verdrahtungsschichten. Typische Werte hierfür sind k < 30. Netzwerk-Probleme: z.B. optimale Positionierung einer „kleinen" Anzahl von Einrichtungen in einem großen Netzwerk. Jüngst weiter ver bessert zu 0(1.271fe ■ n) [8]. 13 Logik- und Datenbank-Probleme: z.B. Eingabe, bestehend aus einer Formel (klein) und einer anderen, großen Struktur (etwa einer Datenbank). Robotik: z.B. beschränkte Anzahl von Freiheitsgraden (typischerweise k < 10) bei komplexen Bewegungs-/Routen-Planungen. Künstliche Intelligenz: z.B. Planungsprobleme. Algorithmische Biologie: z.B. Untersuchung/Vergleich von DNA-Sequenzen der Länge n für k Spezien. Oftmals sind die Parameter auch in den tatsächlich auftretenden Problemen „versteckt" und auf den ersten Blick nicht offenkundig. Als Beispiel hierfür sollen uns wieder einige Probleme der Graphentheorie dienen. Es folgt ein kleiner Exkurs zu speziellen „Weite-Metriken" für Graphen. Definition 2.4. Sei G = {V, E) ein Graph. (i) Eine Baumzerlegung von G ist ein Paar < {Xi \ i g I},T >, wobei Xi c V und T ein Baum mit Knotenmenge aus / ist, so daß gilt: • V Kanten {u, v} g E El i g / : u g Xi und 11 £ lj, • Vi,j,k£l: Falls j auf dem Pfad zwischen i und k in T liegt, so gilt Xi nXk c Xj. Die Weite einer Baumzerlegung < {Xi \ i g I},T > ist definiert als m&xieI{\Xi\ - 1}. (ii) Die Baumweite w{G) von G ist der minimale Wert k, so daß G eine Baumzerlegung der Weite k besitzt. Beispiel 2.5. Beispiele für die Bestimmung von Baumweiten finden sich in den Abbildungen 4 und 5. Aufgabe 2.6. Es sei G = (V, E) ein Graph. 1. Zeige, daß für eine Clique C der Größe k stets gilt: w{C) = k — 1. 2. Sei < {Xi I i g I},T > eine Baumzerlegung von G, dann zeige: 14 c a Graph G± Graph G2 Graph G3 Baumzerlegung für G\. Baumzerlegung für G3: Versuch für G2: {a, b} {a, 6, c, £*, so daß für alle x£E* gilt: x g L 44> f(x) g A. Dabei ist £ ein Eingabealphabet und / wird die Reduktionsfunktion genannt. 17 Beispiel 3.3. Es gilt: Vertex Cover
g L, so nennen wir k den Parameter.
Üblicherweise betrachten wir parametrisierte Probleme speziell als Untermenge von S* x N.
Beispiel 3.6. Wir geben eine Reihe von Beispielen für derartige Problemstellungen.
• Vertex Cover, Independent Set, Dominating Set (zu deren Definition siehe Abschnitt 2.2.1).
• Clique:
Gegeben: Ein ungerichteter Graph Gr = (V, E) und k g N.
Frage: Existiert V c V mit \V'\ > k, so daß V einen vollständigen Teilgraphen in G bildet, d.h. jeder Knoten in V ist mit jedem anderen Knoten in V verbunden.
• MaxSat:
Gegeben: Eine aussagenlogische Formel F in konjunktiver Normalform und k g N.
18
Frage: Existiert eine Belegung, so daß mindestens [y] + k Klauseln wahr sind, wobei m die Anzahl aller Klauseln in F ist? (Bemerkung: Es ist trivial, eine Belegung zu finden, die mindestens [~y] Klauseln erfüllt: Wähle hierzu eine beliebige, zufällige Belegung, dann erfüllt entweder diese, oder ihre Komplementbelegung5 die genannte Voraussetzung.)
• Weighted gCNF Sat:
Gegeben: Eine aussagenlogische Formel F in konjunktiver Normalform mit höchstens q Literalen per Klausel und k g N.
Frage: Hat F eine erfüllende Belegung vom Gewicht k, d.h., eine erfüllende Belegung, bei der genau k Variablen mit „wahr" belegt werden?
• Short NTM computation:
Gegeben: Eine nichtdeterministische Turingmaschine M, ein Eingabewort x für M und k g N.
Frage: Kann M bei Eingabe x eine Endkonfiguration nach höchstens k Schritten erreichen?
Die zentrale Frage, die wir uns stellen, lautet:
Welche dieser Probleme können für „kleines" k „effizient" gelöst werden?
Definition 3.7. Ein parametrisiertes Problem L heißt fixed parameter trac-table, wenn in Laufzeit f{k)nc festgestellt werden kann, ob {x, k) £ L. Dabei seien n := \x\, c eine Konstante unabhängig von sowohl n als auch k, und / : N —> M eine beliebige Funktion.
Die Familie aller fixed parameter tractable parametrisierten Probleme bezeichnen wir mit FPT.
Wie bereits gezeigt, ist Vertex Cover in FPT.
Bemerkung 3.8. • Downey und Fellows unterscheiden in ihrem Buch die Begriffe uniform, streng uniform und nicht-uniform fixed parameter tractable, je nachdem ob man z.B. von der Funktion / Berechenbarkeit verlangt, bzw. ob für jedes k ein anderer Algorithmus zugelassen werden darf. Wir sind hier nur an dem einfachsten Fall interessiert, d.h. ein Algorithmus für k und / in der Regel berechenbar.
5Darunter versteht man jene Belegung, die gegenüber der ursprünglichen Belegung die Variablenwerte 0 und 1 vertauscht.
19
Die Praxisrelevanz von FPT steht und fällt mit der Güte der gefundenen Funktion /; aus konzeptionellen Gründen wird i.a. aber / als beliebig wachsende Funktion zugelassen, also wäre z.B. auch
f(k) = 222
(oder noch „schlimmeres" Wachstum) erlaubt.
20
4 Grundlegende Methoden
Wir lernen nun ein paar Grundtechniken zur Entwicklung parametrisierter Algorithmen kennen.
4.1 Reduktion auf den Problemkern
Grundidee: Reduziere gegebene Probleminstanz X auf eine „äquivalente" Instanz Z7, so daß die Größe von X' allein durch eine Funktion in Abhängigkeit von dem Parameter k beschränkt werden kann. (Danach kann dann in X' etwa die Methode der „erschöpfenden Suche" angewandt werden.)
Beispiel 1: Vertex Cover Der Algorithmus von Buss
Eingabe: Ungerichteter Graph G = (V, E) und k g N.
Ausgabe: Vertex Cover (VC) der Größe < k, falls ein solches existiert.
1. H := {Knoten in G mit mehr als k Nachbarn}; if (\HI > k) then
$ VC der Größe < k; exit eise begin
Lösche alle Knoten in H
(zusammen mit ihren inzidenten Kanten) aus G; k' :=k- \H\;
Lösche alle isolierten Knoten, d.h. Knoten ohne Nachbarn; end;
2. if (resultierender Graph hat mehr als k ■ k' Kanten) then
$ VC der Größe < k; exit;
3. Durchsuche den verbleibenden Graphen nach einem VC der Größe k', z.B. mit Hilfe des in Kapitel 1 beschriebenen, tiefenbeschränkten Suchbaums.
Die zentrale Idee zum Beweis der Korrektheit ist die Feststellung, daß ein Knoten vom Grad > k stets ein Teil des VC der Größe < k sein muß. In Schritt 1 werden all diese Knoten ins VC aufgenommen und es verbleiben k! Knoten, die noch zum gesuchten VC hinzugenommen werden dürfen. Diese können im verbleibenden Graphen in Schritt 2 allerdings maximal
21
Grad k besitzen. Es können mit den verbleibenden k! Knoten also maximal k ■ k' Kanten abgedeckt werden. Wird Schritt 3 erreicht, so liegt ein Graph zugrunde, welcher maximal k • k! < k2 Kanten besitzt.
Hieraus ergibt sich auch die Zeitkomplexität
0(kn + 2kk2),
wobei n := \V\. Der erste Term entspricht dabei der Zeitkomplexität der Schritte 1 und 2. Bei der Wahl geeigneter Datenstrukturen können diese in 0{kn) Schritten ausgeführt werden. Der zweite Term entspricht der Komplexität unseres Suchbaum-Algorithmus aus Kapitel 1 zur Suche eines VC der Größe k' < k, angewandt auf den verbleibenden Restgraphen mit maximal k2 Kanten.
Wir fassen zusammen:
Satz 4.1. Vertex Cover kann in Zeit 0(kn + 2kk2) gelöst werden.
Bemerkung 4.2. • Entscheidende Verbesserungen in der Zeitkomplexität von Vertex Cover wurden durch die Verkleinerung der Suchbaumgröße (in obigem Schritt 3) erreicht (vgl. hierzu [3, 8, 13, 22, 27]).
• Obwohl die Reduktion auf den Problemkern üblicherweise S. Buss [6] zugeschrieben wird, finden sich im wesentlichen gleiche Ideen schon in früheren Arbeiten aus dem Bereich des VLSI-Designs, z.B. [14].
Beispiel 2: Hitting Set für Mengen der Größe 3 (3HS)
Das Problem 3HS ist wie folgt gegeben.
Gegeben: Eine Menge C von dreielementigen Teilmengen einer Menge S und ein k g N.
Frage: Enthält S eine „Hitting Set" für C der Größe höchstens k, d.h. EIS" C S, \S'\ < k, so daß S' mindestens ein Element aus jeder der Mengen in C enthält?
Beachte, daß 2HS genau dem uns bekannten Vertex Cover (VC) entspricht, in diesem Sinn also 3HS eine Erweiterung von VC ist, wo wir uns die „Kanten" als Verbindung von jeweils 3 „Knoten" vorstellen können (Stichwort „Hypergraph"). Wie VC ist auch 3HS NP-vollständig (vgl. [15]).
Soll es ein S' der Größe höchstens k geben, so gelten folgende Beobachtungen:
22
1. Für festes 6 S gibt es höchstens k Mengen der „Form" {x,y,*} (wo * ein beliebiges Element bezeichnet). In der Tat, gäbe es mehr als k Möglichkeiten für *, so muß x oder y in S' sein und damit könnten alle Mengen der Form {x, y, *} aus C entfernt werden.
2. Für festes x G S gibt es höchstens k2 Mengen der Form {x, *, *}, denn: Dank Punkt 1. wissen wir, daß x zusammen mit einem anderen Element y in höchstens k Mengen vorkommen kann. Gäbe es mehr als k2 Mengen, die x beinhalten, so müßte wegen < k folglich x G S' gelten. Damit könnten dann alle Mengen der Form {x, *, *} aus C entfernt werden.
3. Aus 2. folgt insbesondere, daß jedes Element x in höchstens k2 drei-elementigen Mengen auftreten kann. Daraus folgt wegen < k, daß C aus höchstens k • k2 = ks dreielementigen Mengen bestehen kann. Der Problemkern hat also die Größe fc3.
Wir fassen wiederum zusammen:
Lemma 4.3. 3HS besitzt einen Problemkern der Größe 0(fc3). Dieser kann in Zeit linear in der Eingabegröße gefunden werden.
Beweis.
Die Größe des Problemkerns wurde mit obigen Beobachtungen bereits nachgewiesen. Es bleibt also die Zeitschranke zu zeigen: Man überlegt sich leicht, daß man (mithilfe geeigneter Datenstrukturen) leicht zählen kann, wie oft ein Element in den Mengen vorkommt und es gegebenenfalls zusammen mit seinen Mengen aus C löscht. All dies ist in Zeit linear in der Eingabegröße möglich. □
Beispiel 3: Vertex Cover revisited
Einen noch kleineren Problemkern für Vertex Cover (lineare statt quadratische Größe) erhält man dank des folgenden Theorems von Nemhauser und Trotter.
Satz 4.4 (NT-Theorem). Gegeben sei ein Graph G = (V,E) mit n = \V\ Knoten und m = \E\ Kanten. Dann lassen sich in Zeit 0{^/n ■ m) zwei disjunkte Mengen Cq, Vq C V berechnen, die folgende Eigenschaften erfüllen:
(i) Falls eine Menge D C Vq ein Vertex Cover für den durch Vq induzierten Teilgraphen von G ist, so ist C := D U Cq ein Vertex Cover von G.
23
(ii) Es gibt ein optimales Vertex Cover C* von G mit Co C C*.
(iii) Der durch Vq induzierte Teilgraph hat ein minimales Vertex Cover der Mindestgröße ^\Vq\.
Bevor wir nun zum Beweis des NT-Theorems kommen, zunächst seine Anwendung für die Konstruktion eines Problemkerns:
Das NT-Theorem liefert uns eine Menge Cq C V, die Teilmenge eines optimalen Vertex Cover ist. Weiterhin besagt die dritte Eigenschaft aus dem NT-Theorem, daß der „verbleibende Restgraph" von G, der aus den Knoten aus Vq gebildet wird, aus höchstens zweimal so vielen Knoten besteht, wie sein optimales Vertex Cover groß ist. Da die Größe des optimalen Vertex Covers durch k beschränkt sein soll und das NT-Theorem auch die Menge Vq liefert, erhalten wir somit konstruktiv einen aus maximal 2k Knoten bestehenden Problemkern, nämlich den durch die Knoten aus Vq induzierten Teilgraphen von G. Insgesamt erhalten wir somit:
Proposition 4.5. Vertex Cover kann in Zeit O^^fn-m+l^'-k) gelöst werden.
„Schaltet" man dem NT-Theorem noch die Reduktion auf den Problemkern von Buss „vor", so ergibt sich schließlich:
Korollar 4.6. Vertex Cover kann in Zeit 0{kn + k3 + 2kk) gelöst werden.
Es bleibt noch der Beweis des NT-Theorems.
Beweis.
Sei G = (V, E) ein Graph und bezeichne für U C V mit G[U] den durch U induzierten Teilgraphen von G. Weiter sei U' := \v! \ u G U}. Der folgende Algorithmus berechnet die gewünschten Mengen Cq und Vq:
Eingabe: G = (V, E)
Phase 1: Definiere einen bipartiten Graphen6 B = (V, V, EB)
mit der Kantenmenge Eß := {{x,y'} \ {x, y} £ E}. Phase 2: Sei Cß ein optimales Vertex Cover von B,
welches sich über einen Maximum Matching7 Algorithmus
berechnen läßt. Ausgabe: Cq := {x \ x G CB AND x' £ Cß}-
Vq := {x I x G Cß XOR x' G Cß).
24
Wir beweisen nun die Gültigkeit der im NT-Theorem genannten drei Eigenschaften. Definiere dazu
Iq ■= {x\x(£ CßANDx' <£ CB} = V-(V0öCo).
Ad (i):
Für (x, y) g E ist zu zeigen, daß x g C oder y g C. (Zur Erinnerung: C := D U Co, wobei D irgendein Vertex Cover von G[Vq] sei.)
Fall 1: x g Iq, d.h. x,x' g' Cß.
Deshalb muß gelten y,y' g Cb und somit y g Co-Fall 2: y g 70- Analog Fall 1. Fall 3: x g Co oder y g Co- Trivial. Fall 4: x, y g Vo- Dann gilt x g -D oder y g -D.
Ad (ii):
Es ist zu zeigen, daß Co C C* für ein optimales Vertex Cover C*. Dazu setze S = C* und definiere Sy = 3.
Nimm entweder N(v) oder N(a) U N(b) in das Vertex Cover. Denn: Wird v nicht ins VC aufgenommen, so müssen N(v) = {a, b} ins VC genommen werden. Alternativ hierzu kann v ins VC genommen werden; dann müssen — für die Uberdeckung der Kanten {a, v} und {b, v} — die Knoten a und b allerdings nicht mehr ins VC genommen werden. Um dennoch die (weiteren) von a bzw. b ausgehenden Kanten abzudecken, ist allerdings die Aufnahme von N{a) U N(b) unerläßlich. Verzweigungsvektor: (2,3) (beachte, \N(a) UiV(6)| > 3)
Fall 4: El Grad-3-Knoten v mit Nachbarn N(v) = {a, b, c}.
Fall 4.1: El Kante zwischen zwei Nachbarknoten, o.E. zwischen a und b.
~» Nimm entweder N(v) = {a, b, c} oder N(c) in das Vertex Cover.
Denn: Ist v im VC, so muß mind. einer der beiden Nachbarn von a und b drin sein. Wäre auch noch c im VC, so wäre es mind. genau so gut, N{v) selbst zu nehmen. Verzweigungsvektor: (3,3)
Fall 4.2: El gemeinsamer Nachbar d zweier Nachbarn von v, welcher verschieden von v ist. O.E. sei d Nachbar von a und b. ~» Nimm entweder N(v) = {a, b, c} oder {d, v} in das Vertex Cover.
Denn: Nimmt man v und nicht d ins VC, so müßte man a und b nehmen; dann wäre aber wiederum N{v) schon mind. so gut gewesen.
Verzweigungsvektor: (3,2)
Fall 4.3: $ Kante zwischen a, b, c und einer der Nachbarn in N(v) habe Grad > 4. Sei dies o.E. a mit N{a) = {v, a±, a,2, a%}.
Nimm entweder N(v) = {a,b,c} oder N(a) = {v, 01,02,03} oder {a} U N(b) U N(c) in das Vertex Cover. Denn: Nimmt man v und a, so braucht man b oder c nicht mehr hinzuzunehmen, denn z.B. {v, a, b} wäre auf keinen Fall besser als {a, b, c}.
Verzweigungsvektor: (3,4,6) (Beachte hierbei, daß \{a} U N(b) U N(c)\ > 6, denn wegen Fall 4.2 gilt N(b) CiN(c) = {v} und damit
34
\N(b) U N(c)\ > 5. Außerdem gilt a £ N{b) und a £ N{c) wegen Fall 4.1.)
Fall 4.4: sonst, d.h. es gibt keine Kante zwischen Elementen aus
N{v) und alle Elemente aus N{v) besitzen genau Grad 3.
~» Nimm entweder N{v) = {a, b, c} oder N(a) = {v, a±, a2} oder
N(b) U N(c) U N(a1) U N(a2) in das Vertex Cover.
Denn: Im letzten „Zweig" muß man a und v nehmen. Dann macht
es „keinen Sinn" mehr, b und c zu nehmen, also wähle N(b)\JN(c).
Analog argumentiert man mit vertauschten Rollen für a und v,
was zur Aufnahme von N(a±) U N(a,2) führt.
Verzweigungsvektor: (3,3,6) (Beachte hierbei, daß N(b) D N(c) =
{v}, also |iV(6) U N(c)\ = 5, und es ist a G N{a{) und a ^
N(b)UN(c).)
Fall 5: Der Graph ist 4-regulär, d.h. jeder Knoten hat genau 4 Nachbarn.
~» Wähle beliebigen Knoten v, nimm entweder v oder N(v) in das VC. Verzweigungsvektor: (1,4).
Die zentrale Beobachtung hierbei ist es, daß dieser Fall nur einmalig während des Ablaufs des gesamten Suchbaum-Algorithmus auftritt. Wird nämlich nach v bzw. N(v) verzweigt, so müssen die entstandenen Teilgraphen immer mind. einen Knoten vom Grad < 3 enthalten. Dieser Fall spielt also asymptotisch keine Rolle.
Damit haben wir eine vollständige Fallunterscheidung. Zusammenfassend erhalten wir als Verbesserung von Satz 4.1.
Satz 4.15. Vertex Cover kann in Zeit 0{kn + (1.342)fc • k2) gelöst werden. Beweis.
Bis auf die Größe des neuen Suchbaum schließt man analog zum Nachweis der Zeitkomplexität in Satz 4.1. Es bleibt also die Größe des neuen Suchbaums abzuschätzen. Diese ist durch die zu den jeweiligen Fällen gehörige Rekursionsgleichungen bestimmt. Diese wiederum sind eindeutig aus den Verzweigungsvektoren zu errechnen.
Wir finden
35
Fall Verzweigungs- errechnete Basis
vektor der Baumgröße
1 2 (1,5) 1.325
3.1 - -
3.2 - -
3.3 (2,3) 1.325
4.1 (3,3) 1.260
4.2 (3,2) 1.325
4.3 (3,4,6) 1.305
4.4 (3,3,6) 1.342
5 (1,4) 1.381
Da wir wegen des maximal einmaligen Auftretens von Fall 5 diesen für die asymptotische Zeitkomplexität vernachlässigen können, liefert Fall 4.4 den worst case mit einer Baumgröße von (1.342)k. □
Bemerkung 4.16. • In Satz 4.15 (und auch allgemeiner für Methoden bestehend aus Reduktion auf den Problemkern und Suchbaum) läßt sich durch einfache Modifikation am Algorithmus und verbesserter mathematischer Analyse der Faktor k2 durch eine kleine Konstante ersetzen (vgl.[21]). ertex Cover ist demgemäß sogar in Zeit 0(kn+(1.342)k) lösbar. Analog kann man in Satz 4.14 den Faktor fc3 verschwinden lassen.
• Die besten derzeit bekannten parametrisierten Algorithmen für Vertex Cover erreichen eine Suchbaumgröße deutlich unter (1.3)fc (vgl. hierzu [22, 27, 8]).
• Der beste „nicht-parametrisierte", exakte Algorithmus für Vertex Cover hat Laufzeit 0(1.211n), wobei n die Anzahl der Knoten im Graphen G ist (vgl. [25]).
4.3 Verflechtung von Problemkernreduktion und Suchbaummethode
Sei (/, k) die Eingabeinstanz eines parametrisierten Problems. Nehmen wir weiter an, daß ein Lösungsalgorithmus mit Laufzeit 0{P{\I\) + R(q(k))^k) existiert, der erst in Zeit P(|/|) einen Problemkern der Größe q{k) erzeugt und dann R{q{k)) Zeit benötigt, um einen Knoten des Suchbaums (der Suchbaum habe Größe 0(£k), wobei £ eine Konstante ist) zu expandieren. Wir haben hier also eine klare Trennung in Phase 1 (Problemkernreduktion) und Phase 2 (Suchbaum). Nachfolgend zeigen wir, wie sich durch eine Verflechtung beider Phasen obige Laufzeit auf 0(P(\I\) + £fc) verbessern läßt. Dazu benutzen wir folgenden erweiterten Algorithmus zur Expandierung eines
36
Suchbaumknotens (/, k). Wir setzen dabei voraus, daß (/, k) über die rekursiven Aufrufe bezüglich der Instanzen {Ii,k — d±),..., {Im, k — dm) gelöst wird.
if \I\> c - q(k)
then führe Problemkernreduktion für (/, k) durch; ersetze (/, k) durch
{Ii, k — di),..., {Im, k - dm).
Hierbei ist c eine geeignet zu wählende Konstante. Neu ist bei obiger Expandierung die if-Abfrage, die bewirkt, daß auch „inmitten des Suchbaums" wiederholt eine Problemkernreduktion durchgeführt wird. Nun kurz zur (Andeutung einer) mathematischen Analyse dieser modifizierten Rekursion. Wir bekommen folgende Rekursionsgleichnug zur Abschätzung des Zeitaufwandes zur Abarbeitung von (/, k):
Tk = Tk_dl + ...+ Tk_dm + 0{P{q{k)) + R{q{k))).
Der O-Term schätzt dabei die Zeit zur Expandierung von (/, k) ab. Hierbei handelt es sich nun um eine lineare Rekursionsgleichung mit konstanten Koeffizienten und Inhomogenität (nämlich der O-Term). Die allgemeine Lösung einer solchen Rekursionsgleichung ergibt sich aus der allgemeinen Lösung der zugehörigen homogenen Rekursionsgleichung (ohne den O-Term) und einer speziellen Lösung der gegebenen Gleichung. Für die homogene Rekursionsgleichung wissen wir, daß alle Lösungen von der Form 0(£fc) sind. Wir suchen noch eine spezielle Lösung der Gleichung mit Inhomogenität. Da die Inhomogenität ein Polynom ist, existiert auch eine spezielle Lösung, die ein Polynom in k ist und darüberhinaus den selben Grad wie die Inhomogenität besitzt. Insgesamt folgt damit, daß alle Lösungen von Tk durch 0(£fc) beschränkt sind.
Abschließend wollen wir noch ein einfaches Beispiel beruhend auf Vertex Cover betrachten, welches zeigt, wie die Verflechtung von Problemkernreduktion und Suchbaum verbessernd wirkt. Wir setzen dabei den naiven 2k-Suchbaum-Algorithmus (vgl. Kapitel 1) voraus und die Problemkernreduktion sei diejenige von Buss (vgl. Abschnitt 4.1, Beispiel 1; Idee: Knoten vom Grad > k müssen in ein Vertex Cover genommen werden). Unser Graph bestehe aus einem „Kopf" mit {k — l){k — 2) + l Knoten und einem „Schwanz" mit 3fc + 1 Knoten, insgesamt also aus k2 + 4 Knoten. Für k = 15 ist er in Abbildung 6 gezeichnet.
Man überzeugt sich leicht, daß ein minimales Vertex Cover für diesen Gra-phendie Größe |fc — | hat, also die Frage nach einem Vertex Cover der Größe k immer mit nein beantwortet werden muß. Die Buss'sehe Reduktion auf den Problemkern hat keine Wirkung auf diesen Graphen, da kein Knoten Grad > k hat. Fängt der Suchbaumalgorithmus mit Kanten von „rechts
37
Abbildung 6: Beispielgraph mit k = 15.
nach links" (siehe Abbildung 6) an, so bleibt der Kopf immer unverändert und so sind die Kosten pro Expandierung immer 0{k2). Die Gesamtlaufzeit ist damit im schlimmsten Fall ®(k2 ■ 2k). Wendet man jedoch unsere Verflechtungstechnik an, so ist nach Entfernung der zweiten Kante aus dem Graphen der Parameter k um 2 erniedrigt und dadurch wird schließlich der ganze Kopf per Problemkernreduktion aus dem Graphen entfernt.
4.4 Farbkodierungen und Hashing
In diesem Abschnitt besprechen wir eine Methode, die nicht mehr so „elementar" ist wie z.B. die Suchbaummethode, jedoch mitunter fast vergleichbar gute Laufzeitwerte (exponentieller Faktor!) liefert.
Zur Illustration betrachten wir folgendes Problem, das im allgemeinen NP-vollständig ist (vgl. [15]):
Longest Path:
Gegeben: Ein ungerichteter Graph G = (V, E) und ein k G N. Frage: Gibt es einen einfachen Pfad der Länge k — 1 in G, d.h. einen Pfad bestehend aus k Knoten, so daß kein Knoten zwei oder mehrmals auf dem Pfad auftaucht?
Bemerkung 4.17. • Eine Variante des obigen Problems, das sogenannte Longest Cyc/e-Problem, welches ebenfalls zu den iVP-vollständigen Problemen gehört, wäre im folgenden analog zu behandeln.
• Uber das Bilden der k-ten Potenz der sogenannten Adjazenzmatrix lassen sich (mit algebraischen Mitteln) all die Knotenpaare zu finden, welche durch Pfade der Länge k miteinander verbunden sind. In der Regel sind die so gefundenen Pfade allerdings nicht einfach.
38
Wir beschreiben zunächst einen randomisierten Ansatz zur Lösung von Lon-gest Path:
Färbe die Knoten von G per Zufall mit k verschiedenen Farben. Wir nennen einen Pfad voll bunt, wenn jeder seiner Knoten mit einer anderen Farbe gefärbt wurde.
Offensichtlich ist jeder voll bunte Pfad einfach. Umgekehrt gilt: Jeder einfache Pfad der Länge — 1 ist mit Wahrscheinlichkeit > e~k voll bunt.
Lemma 4.18. Es sei G = (V,E) ein Graph und c : V —> {l,...,k} sei
eine Färbung seiner Knoten mit k verschiedenen Farben. Dann kann ein voll bunter Pfad der Länge k — 1 in G (falls ein solcher existiert) in Zeit 2°(k) ■ \E\ gefunden werden.
Beweis.
Nachfolgend beschreiben wir einen Algorithmus, der alle voll bunten Pfade der Länge k — 1 ausgehend von einem Startknoten s findet. Dies ist keine Einschränkung, denn um das allgemeine Problem zu lösen, fügen wir einfach einen neuen Knoten s' zu V hinzu, färben ihn mit der neuen Farbe 0 und verbinden ihn mittels Kanten zu jedem Knoten aus V.
Der nachfolgende Ansatz beruht auf der Methode des Dynamischen Programmierens.
Annahme: Vt) G V wurden bereits alle möglichen Farbmengen von voll bunten Pfaden zwischen s und v mit Länge i gefunden.
Wichtig: Nicht die Pfade, sondern nur die Farbmengen werden gespeichert. Für jeden Knoten v gibt es jeweils höchstens (^) viele solcher Mengen. Sei nun C eine solche Farbmenge, die zu v gehört. Wir betrachten jedes zu v gehörende C und jede Kante {u, v} £ E: Füge c(u) zu C hinzu, falls c(u) g' C. So erhalten wir alle möglichen Farbmengen, die zu Pfaden der Länge i + 1 gehören, usw. Damit erhält G einen voll bunten Pfad bezüglich der Färbung c, genau dann wenn es einen Knoten v G V gibt, der mindestens eine Farbmenge besitzt, die zu einem Pfad der Länge k — 1 korrespondiert.
Zeitkomplexität: Der beschriebene Algorithmus führt 0(X^=i*(i) " Operationen aus. Dabei entspricht der Faktor i jeweils dem Test, ob c(u) schon in C liegt. Der Faktor (^) gibt die Anzahl der möglichen C-Mengen an, und der Faktor \E\ wird benötigt, um den Test {u,v} £ E durchzuführen. Der gesamte Ausdruck läßt sich, wie behauptet, durch 0(k2k\E\) abschätzen. □
Aufgabe 4.19. Wie wird im obigen Beweis der gesuchte Pfad tatsächlich konstruiert?
Satz 4.20. Longest Path kann in „erwarteter" Laufzeit 2°^ ■ \E\ gelöst werden.
39
Beweis.
Nach obigen Vorbemerkungen ist mit Wahrscheinlichkeit > e~k ein einfacher Pfad der Länge k — 1 voll bunt. Nach Lemma 4.18 kann ein solcher voll bunter Pfad in Zeit 2°^ ■ \E\ gefunden werden; genauer ergibt sich hieraus auch, daß alle voll bunten Pfade der Länge k — 1 gefunden werden können.
Wiederholen wir also folgenden Vorgang ek = 2°^ mal:
1. Wähle per Zufall eine Knotenfärbung c:v—>{1,...,&}.
2. Uberprüfe mit Lemma 4.18, ob es einen voll bunten Pfad gibt; falls ja, so ist dies ein einfacher Pfad der Länge k—1.
Nach ek Wiederholungen ist der Erwartungswert für die gefundenen voll bunten Pfade (falls solche existieren) größer als ek ■ e~k = 1. Also kann Longest Path in erwarteter Laufzeit ek -2°^ ■ \E\ = 2°^ ■ \E\ gelöst werden.
□
Der in Satz 4.20 beschriebene Algorithmus ist randomisiert („erwartete Laufzeit"). Mit Hilfe von Hashing kann er mit geringen Effizienzeinbußen in einen deterministischen umgewandelt werden.
Zur Erinnerung rekapitulieren wir die Grundidee beim Hashing. Ziel dieser Methode ist es, „wenige" Elemente eines „großen Raums" eindeutig auf einen „kleinen Raum" abzubilden. Anwendungen dieser Technik finden sich z.B. im Compilerbau, wo etwa das Anlegen einer Symboltabelle für die Variablen eines Programms über Hashtabellen geregelt wird.
Für unsere Zwecke benötigen wir folgendes:
Eine Liste von Färbungen der Knoten V eines Graphen, so daß für jede Teilmenge V C V der Größe k gilt: Es gibt mindestens eine Färbung in dieser Liste derart, daß jeder Knoten in V eine andere Farbe hat.
Dies läßt sich mit dem Begriff der fc-perfekten Familien von Hash-Funktionen von {1, 2,..., I V|} nach {1, 2,..., k} formalisieren:
Definition 4.21. Eine k-perfekte Familie von Hash-Funktionen ist eine Familie T von Funktionen von {1,..., n} nach {1,..., k} derart, daß zu jeder Teilmenge S C {1,... ,n} mit \S\ = k ein / G T existiert, so daß / auf S bijektiv ist.
Mittels tiefliegender mathematischer Methoden, welche den Rahmen dieser Vorlesung sprengen würden, läßt sich zeigen (vgl. etwa [1]):
40
Mitteilung 4.22. Es ist möglich, Familien k-perfekter Hash-Funktionen von {1,..., n} nach {1,..., k} zu konstruieren, die aus 2°^ logn vielen Elementen bestehen.
Hinweis 4.23. Für ein / aus der in Mitteilung 4.22 beschriebenen Familie fc-perfekter Hash-Funktionen läßt sich f{i) (mit 1 < i < n) in linearer Zeit berechnen.
Satz 4.24. Longest Path kann deterministisch in Laufzeit 2°^ ■ \E\ - log \ V\ gelöst werden. Insbesondere ist also Longest Path in FPT.
Beweis.
Färbe den Graph mittels aller möglicher Hash-Funktionen aus der in Mitteilung 4.22 gegebenen Familie. Nach Definition 4.21 muß bei mindestens einer dieser Färbungen ein einfacher Pfad voll bunt werden. Ein voll bunter Pfad läßt sich dann wieder mit Lemma 4.18 finden.
Da die Familie aus Mitteilung 4.22 aus 2°^ logn vielen Elementen besteht, muß die Komplexität des Algorithmus in Lemma 4.18 mit diesem Faktor multipliziert werden. Somit erhalten wir die Gesamtlaufzeit
2°W logn • 2°W\E\ = 2°W\E\log \V\,
wo n = \ V\. □
Hashing allein schon kann helfen, FPT-Algorithmen anzugeben:
Zur Illustration betrachten wir das im allgemeinen iVP-vollständige Multi-dimensional Matching Problem:
Gegeben: Eine Menge M C X\ x ... x Xr, wobei X{ paarweise disjunkte Mengen sind und k G N.
Frage: Existiert M' C M mit \M'\ = k, so daß keine zwei Elemente in irgendeiner Koordinate übereinstimmen?
Satz 4.25. Multidimensional Matching kann in Zeit 0{20^kr\kr)\nr log2 n) gelöst werden, d.h. Multidimensional Matching ist in FPT.
Beweis.
Sei ./V die Anzahl aller verschiedenen Koordinaten, die in der Eingabe M auftreten. Ohne Einschränkung läßt sich also die Menge aller Koordinatenwerte durch {1,..., N} repräsentieren. Desweiteren setze K := kr. Schließlich bezeichne n die Gesamt große der Beschreibung von M, sprich die Eingabegröße.
41
Definiere ein Lösungsschema S als eine Menge von k vielen r-Tupeln, so daß die Vereinigung aller Koordinaten genau {1,..., K} ergibt.
Sein nun 7i(N, K) eine Familie fc-perfekter Hash-Funktionen von {1,..., TV} nach {1,..., K} (vgl. Definition 4.21 und Mitteilung 4.22).
Folgender Algorithmus löst das Multidimensional Matching Problem:
for alle h G T~C(N, K) und alle Lösungsschemata S do
for alle a G M mit a = (a±,..., ar), ctj G {1,... ./V} do
berechne (h(a±),..., h(ar)); if jedes r-Tupel in S erscheint als Bild (h(ai),..., h{ar)) für ein a = (a±,..., ar)
then Multidimensional Matching hat eine Lösung bestehend aus „diesen" a's; if in voriger Schleife wurde keine Lösung gefunden
then Multidimensional Matching hat keine Lösung;
Zur Korrektheit des Algorithmus: Falls M ein „fc-Matching" besitzt, dann beinhaltet das K = kr verschiedene Koordinaten und nach Mitteilung 4.22 existiert ein h G 7i(N,K), so daß diese bijektiv auf {1,...K} abgebildet werden; das Bild unter h ist dann ein gesuchtes Lösungsschema S. Existiert umgekehrt ein h, welches ein Lösungsschema wie beschrieben als Bild liefert, dann ergibt das Urbild unter h wiederum ein „k-Matching".
Zur Laufzeit des Algorithmus:
• Nach Mitteilung 4.22 besteht H{N,K) aus 2oi-K"> ■ log TV vielen Hash-funktionen.
• Es gibt K\ Möglichkeiten für Lösungsschemata.
• Es gibt 0{n) viele Elemente a.
• Die Berechnung von (h(ai),..., h{ar)) läßt sich in Zeit 0{r logN) durchführen.
Zusammen erhalten wir also die behauptete Laufzeit
0{20{K) -\ogN -Kl -n-rlogN) =0{20{K) • K\ • n • r • log2 n).
□
Wir wollen abschließend zur Hashing-Methode bemerken, daß die exponen-tielle Komponente des parametrisierten Algorithmus in der Regel (auch) von der Größe der Hashfamilie abhängt.
42
4.5 Beschränkte Baumweiten
In diesem Kapitel greifen wir nochmals die Idee der Baumzerlegung eines Graphen auf. Dazu rufen wir uns noch einmal die grundlegende Definition hierzu in Erinnerung (siehe Definition 2.4).
Die entscheidende Beobachtung für den Ansatz, den wir in diesem Abschnitt diskutieren, ist nun: Viele im allgemeinen iVP-vollständige Graphenprobleme können in Polynomialzeit, meist sogar in Linearzeit, gelöst werden, wenn man diese auf die Klasse der Graphen beschränkt, die eine vorgegebene Baumweite nicht überschreiten. Insbesondere ist dies der Fall, wenn die zugehörige Baumzerlegung bekannt ist.
Typischerweise ergibt sich dadurch folgender Grundansatz zur Gewinnung von FPT-Algorithmen:
1) Ermittle eine Baumzerlegung des Eingabegraphen.
2) Wende einen Polynomialzeitalgorithmus an, welcher auf der Baumzerlegung beruht.
Wir werden in diesem Kapitel beide Aspekte am Beispiel von Vertex Cover diskutieren.
4.5.1 Dynamisches Programmieren bei gegebener Baumzerlegung
Zunächst greifen wir den 2. Schritt obiger Strategie auf und zeigen folgendes Resultat.
Satz 4.26. Für einen Graphen G mit gegebener Baumzerlegung X = ({Xi : i G Vr}, T) kann ein optimales Vertex Cover in Zeit 0(2^^ • \ Vt\) gefunden werden. Hier bezeichnet u)(X) die Weite der Baumzerlegung X.
Beweis.
Wir geben einen Algorithmus an, welcher im wesentlichen auf dem Paradigma des „Dynamischen Programmierens" basiert. Grundidee ist es, für jedes der \Vr\ vielen Bags Xi „naiv" alle 2^*1 Möglichkeiten zur Gewinnung eines Vertex Cover auf dem durch Xi induzierten Teilgraphen G[ATj] auszuprobieren. Dies geschieht in entsprechenden Tabellen Ai (i G Vr)- In einem 2. Schritt werden diese Tabellen gegeneinander abgeglichen. Wir arbeiten uns dabei von den Tabellen, die zu den Blättern von T gehören, schrittweise zur Tabelle der Wurzel vor. Durch den angesprochenen „Abgleich" der Tabellen untereinander stellen wir sicher, daß wir von den „lokalen" Lösungen auf den Graphen G[ATj] zu einer „globalen" Lösung auf G gelangen. Im einzelnen verfährt der skizzierte Algorithmus wie folgt:
43
Schritt 0: Zu jedem Xi = {x^,... ,%in.}, \Xi\ = rij, erstelle eine Tabelle
Xi± Xi2 m
0 0 • 0 0
0 0 • 0 1 >
1 1 . 1 0
1 1 . 1 1
Die Tabelle hat 2*H Zeilen und \rii \ +1 Spalten. Jede Zeile repräsentiert eine sogenannte „Färbung" der Teilgraphen Darunter verstehen
wir eine 0—1 Sequenz der Länge rij, welche angibt, ob die jeweiligen Knoten aus Xi in das aktuelle Vertex Cover aufgenommen werden (= „1") oder nicht aufgenommen werden (= „0"). Formal ist eine Färbung eine Abbildung
C« : Xi = {xil,...,xini}^{0,l}.
Die Tabelle hat für jede mögliche der 2ni Färbungen einen zusätzlichen Spalteneintrag.
Die letzte Spalte speichert (für eine jede solche Färbung C^) die Anzahl m(C^) der Knoten, die ein minimales Vertex Cover benötigen würde, welches die Knoten aus Xi entsprechend der Färbung beinhalten würde, das heißt
m(C''') = minJlF'l : V' C V ist ein Vertex Cover
für G, so daß v e V' für alle v G 1 (1)
und v <£ V' für alle v G (c^ 1 (0)}.
Die Beschreibung dieses Werts geschieht durch das Dynamische Programmieren in nachfolgendem Schritt 2.
Natürlich muß nicht jede Färbung ein Vertex Cover „zulassen", das heißt für eine gegebene Färbung ist es möglich, daß kein Vertex Cover V C V existiert, so daß
v G V für alle v G 1 (1) und
v i V' für alle v G (c^1 (0). Eine solche Färbung heißt „ungültig".
Nachfolgender Algorithmus überprüft Färbungen auf deren Gültigkeit:
bool is-valid (Färbung CW : Xi -> {0,1})
result = true;
for (e = {u,v} G EG[Xi])
if (CW(«)=0ACW(u) = 0) then result = false;
44
Schritt 1: Initialisiere die Tabellen:
Für alle Tabellen Xi und eine jede Färbung : Xi —> {0,1} setzen wir
(CW) 1 (1) , falls (is.valid (C«)) +oo, sonst
Schritt 2: Dynamisches Programmieren:
Wir arbeiten uns nun im Baum T der Baumzerlegung von den Blättern zur Wurzel nach oben und „gleichen" die jeweiligen Tabellen Xi gegeneinander ab.
Sei j G Vt der Elternknoten von i £ Vr- Wir zeigen, wie die Tabelle Xj durch jene von Xi „aktualisiert" wird. Dazu nehmen wir an, daß
Xi = {zi,... ,zs,ui,... ,uti} Xj = {zi,...,zs,vi,...,vti},
also Xif]Xj = {zi,..., zs}.
Für jede mögliche Färbung
C: {Zl,...,zs}^{0,l} und jede Erweiterung6 : Xj —> {0,1} setzen wir m
+ min{ m(C(i)) | CW : Xi -> {0,1} Erweiterung von C}
-\c-\i)\
(i)
Zusätzlich merken wir uns an dieser Stelle, welche Färbung Ci : Xi —> {0,1} zur Bildung des Minimums in (*) gewählt wurde. Das bedeutet: Wir „verzeigern" die Zeile der Färbung in Tabelle Xj
(i)
mit der Zeile der Färbung C* in Tabelle Xi. Auf diese Weise werden alle Einträge der letzten Spalte in Aj durch jene von Ai „aktualisiert".
Hat ein Vektor j G Vr mehrere Kinder £ Vt, so wird die
Tabelle Aj sukzessive gegen alle Tabellen A^,..., Ail (auf diese Weise) aktualisiert.
Der Schritt des dynamischen Programmierens wird durchgeführt, bis wir die Tabelle des Wurzelknotens „aktualisiert" haben.
6Unter einer Erweiterung einer Färbung C : W —> {0,1} (wo W C V) verstehen wir eine Färbung C : W -> {0,1} mit W 2 W und C\w = C.
45
Schritt 3: Konstruktion eines optimalen Vertex Cover:
Die Größe eines optimalen Vertex Cover ergibt sich aus dem Minimum der Einträge der letzten Spalte der Tabelle Ar des Wurzelknotens r 6 VT.
Die zugehörige Färbung dieser Zeile gibt an, welche der Knoten des „Wurzelbags" Xr in diesem optimalen Vertex Cover enthalten sind. Haben wir uns im Verlauf von Schritt 2 bei der „Aktualisierung" in Formel (1) noch zusätzlich „gemerkt" wie die Bildung des Minimums zustande kam, so können wir nun durch Verfolgen der Verzweigung die zugehörige Färbung der Knoten in allen bags von X (und damit die Gestalt dieses optimalen Vertex Covers) rekonstruieren.
Zur Korrektheit des Algorithmus:
a) Bedingung (1) der Definition (siehe Definition 2.4) einer Baumzerlegung (V = UieVr ^) stellt sicher, daß jeder Knoten in der Berechnung berücksichtigt wurde.
b) Bedingung (2) einer Baumzerlegung (Ve 3io : e £ Aj0) stellt sicher, daß nach der Behandlung der „ungültigen" Färbungen in Schritt 0 im Verlauf der Berechnung nur noch tatsächliche Vertex Cover berücksichtigt werden.
c) Bedingung (3) einer Baumzerlegung garantiert die „Konsistenz" des dynamischen Programmierens:
Sollte ein Knoten v G V in zwei verschiedenen bags und Aj2 auftauchen, so ist ausgeschlossen, daß für das errechnete optimale Vertex Cover dieser Knoten in den jeweiligen Tabellen bzw. Ai2 zwei unterschiedliche Farben zugewiesen bekommt. Dieser Konflikt hätte sich spätestens in bag Aj0 eines kleinsten gemeinsamen Vorfahren i$ von i\ und ?2 in T aufgelöst. Denn laut Bedingung (3) der Baumzerlegung muß v ja auch in Aj0 auftauchen.
Zur Laufzeit des Algorithmus:
Bei geschicktem Umsortieren der Tabellen kann das Aktualisieren einer Tabelle Aj durch die Tabelle Ai in Zeit
0(#Zeilen von Ai + #Zeilen von Aj) = 0(2|Xi| + 2|x>'1) = 0(2w(x)) durchgeführt werden.
Für jede Kante e £ Et in Baum T muß ein Abgleich zweier Tabellen stattfinden, das heißt die Gesamtlaufzeit des Algorithmus ist gegeben durch
0(2^ • \Et\) = 0(2^ • \VT\).
□
46
Ähnliche Resultate wie jene von Satz 4.26 erhält man für eine Vielzahl von Graphenproblemen. Die Methode des „Dynamischen Programmierens" bei gegebener Baumzerlegung liefert etwa
Mitteilung 4.27. Für einen Graphen G mit gegebener Baumzerlegung X können
a) Vertex Cover in Zeit 0(2^ -\VT\),
b) Independent Set in Zeit 0(2^ -\VT\),
c) Dominating Set in Zeit 0(4"^) • |Vr|),
berechnet werden. Hier bezeichnet die Weite der Baumzerlegung X und
\Vt\ ist die Anzahl der Knoten des Baumes T der Zerlegung X.
4.5.2 Konstruktion von Baumzerlegungen
Es bleibt die Frage zu klären, wie man bei gegebenem Graphen eine Baumzerlegung (mit möglichst kleiner Baumweite) erhalten kann. Hierzu zitieren wir folgendes (tiefliegendes) Ergebnis von Bodlaender [5].
Mitteilung 4.28. Es gibt einen Algorithmus mit Laufzeit 0(f(k) -n), welcher für einen gegebenen Graphen überprüft, ob er Baumweite höchstens k besitzt. Falls ja, so liefert der Algorithmus darüber hinaus auch eine zugehörige Baumzerlegung.
Es muß angemerkt werden, daß der zu Mitteilung 4.28 gehörige Algorithmus (siehe [5]) sehr aufwendig ist und große konstante Faktoren mit sich bringt (es ist etwa f(k) = 235fc2). Es ist ein aktuelles Forschungsthema, die Effizienz eines solchen Algorithmus zu verbessern.
Um nun einen parametrisierten Algorithmus für ein parametrisiertes Problem wie Vertex Cover zu erhalten, müssen wir die Mitteilungen 4.27 und 4.28 miteinander verschmelzen. Um dies ermöglichen zu können, bedarf es einer Beziehung zwischen der Baumweite eines Graphen und dem problemspezifischen Parameter. Es gilt beispielsweise für Vertex Cover.
Lemma 4.29. Sei G ein Graph, welcher ein Vertex Cover der Größe vc(G) besitzt, dann gilt: tw(G) < vc(G).
Beweis.
Es sei V C V ein Vertex Cover von G = (V,E) mit \V'\ = vc(G). Wir geben eine Baumzerlegung X mit uj(X) < vc(G) an. Es sei D := V \ V =
47
{vi±,... Als Baumstruktur T wählen wir einen Pfad der Länge \D\,
d.h. T = (1, 2,...,\D\ - 1,\D\). Weiter definiere Vj := V U {v^} für alle j = l,...,\D\.
Zu zeigen bleibt, daß X := ({Vi : i g Vr},P) in der Tat eine Baumzerlegung von G bildet (beachte, daß uj(X) = maxjeyT \ Vi\ — 1 = vc(G)).
Wir überprüfen die 3 Eigenschaften aus Definition 2.4:
1. Für alle v g V gilt entweder v g V oder d £ D. In beiden Fällen ist jedoch v g UieyT ^.
2. Sei {«, g E. Da V' ein Vertex Cover ist, können wir ohne Einschränkung annehmen, daß u g V.
Fall 1: v g V {u, v} c ^ für alle j = 1,..., \D\.
Fall 2: v <£ V ^> v = vh für ein Z g {1,...,\D\} => {u,v} c V;.
3. Sei v g und » £ ^ für ?i 7^ dann gilt nach Konstruktion
v g V c Fn nVi2.
□
Damit erhalten wir folgenden Algorithmus zur Lösung des parametrisierten Vertex Cover Problems:
input: Graph G und Parameter k. if (tw(G) > k) then
Output („Es gibt kein Vertex Cover der Größe < fc")7 eise begin
Berechne eine Baumzerlegung X von G.s
Löse Vertex Cover durch „Dynamisches Programmieren" auf X.9
end
Die Effizienz eines solchen Algorithmus hängt von zwei wichtigen Größen ab:
• Der Größe der Baumweite für die „ Ja"-Instanzen des Problems, d.h. von der Güte einer Abschätzung wie jener in Lemma 4.29.
7Die Korrektheit dieses Schritts gilt nach Lemma 4.29. 8Berechnung der Baumzerlegung nach Mitteilung 4.28. 9Dynamisches Programmieren nach Satz 4.26.
48
• Der Laufzeit des Algorithmus zur Konstruktion einer Baumzerlegung (d.h. der Güte des Algorithmus aus Mitteilung 4.28).
Wie schon angesprochen ist es Gegenstand aktueller Forschung, Resultate in diese Richtung zu verbessern. Man ist jedoch nicht immer auf Mitteilung 4.28 angewiesen. Für den Fall von planaren10 Graphen konnte — mit der Technik sogenannter Graphseparatoren — folgendes gezeigt werden (siehe [?]).
Mitteilung 4.30. Sei G ein planarer Graph. Es bezeichne vc(G) die Größe eines minimalen Vertex Covers von G und "f(G) die Größe einer minimalen Dominating Set von G. Dann gilt:
tw(G) < c\ • yjvc(Gr) und tw(G) < c2-y/^G).
Eine Baumzerlegung der entsprechenden Weite kann in Zeit 0(vc(G)3/2-n), bzw. 0(7(G)3/2 • n) gefunden werden.
Die bisher nachgewiesenen Konstanten sind c\ = 4-\/3 und c2 = 6-\/34.
Auf diese Weise ergeben sich — unter Hinzunahme der Ergebnisse aus Mitteilung 4.27 — nach dem eingangs erwähnten Schema Algorithmen der Laufzeit
• 0(2Cl^n) zum Lösen von planarem Vertex Cover.
• 0(4C2^n) zum Lösen von planarem Dominating Set.
Zum Schluß des Abschnitts wollen wir nochmals eine „Intuition für die Grundidee der Baumzerlegung" geben: Es ist hilfreich sich vorzustellen, daß eine Baumzerlegung eine Art „Landkarte" der Struktur (und Analyse) eines Graphens darstellt. Oftmals geben die Baumknoten der Zerlegung — diese entsprechen einer Menge von Knoten des ursprünglichen Eingabegraphen — an, welche Information ein Algorithmus jeweils „halten" muß. Als Schlagwörter seien hier etwa „Parse-Bäume" oder „Baum-Automaten" gen-nannt.
Beispielsweise besagt ein Satz von Courcelle [10], daß jede Grapheneigenschaft, die sich in sog. monadischer Logik 2.Stufe ausdrücken läßt, für beschränkte Baumweiten erkennbar ist. Genauer bedeutet „erkennbar", daß im Fall von Eingabegraphen mit beschränkten Baumweiten ein Baumautomat angegeben werden kann, welcher erkennt, ob der Graph die besagte Eigenschaft hat. Auf diese Weise kann nach obigem Schema ein FPT-Algorithmus für derartige Eigenschaften konstruiert werden.
10Ein planarer Graph ist ein Graph, welcher sich ohne Kantenüberschneidungen in der Ebene zeichnen läßt.
49
4.6 Graphminoren
In diesem Abschnitt soll kurz eine mathematisch wesentlich tiefliegende und recht aufwendige Methoden zur Gewinnung parametrisierter Algorithmen dargestellt werden. Eine halbwegs erschöpfende Darstellung dieser Methoden bedürfte einer eigenen Vorlesung. Darüberhinaus ist die hier vorgestellte Methode eher von theoretischem Interesse, da sie bislang offenbar noch nicht zu effizienten parametrisierten Algorithmen führt.
Es handelt sich im wesentlich um die Verallgemeinerung eines Satzes von Kuratowski, welcher besagt, daß ein Graph genau dann planar ist, wenn er nicht die Minoren K^^ (vollständiger bipartiter Graph der Größe 3,3) und K§ (vollständiger Graph der Größe 5) besitzt.
Definition 4.31. Ein Graph H heißt Minor eines Graphen G (in Zeichen H