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 kl (Maximierungsproblem) Frage b): Ely G Sq{x) mit fQ{x,y) < kl (Minimierungsproblem) Definition 5.3. 1. Ein NP-Optimier ungsproblem (Iq, Sq, /q, optg) hat einen e-Approximationsaigorithmus, falls es für jedes x G Iq einen Polynomzeit-Algorithmus gibt, der ein y G Sq(x) ausgibt mit der Eigenschaft \fQ{x,y) -optQ(x)| --- <- £. m&x{optQ(x),fQ(x,y)} 53 2. Ein NP-Optimierungsproblem Q hat ein Polynomzeit-Approximationsschema (polynomial time approximation scheme, kurz: PTAS), wenn es für jedes e > 0 und jedes x G Iq einen Polynomzeit e-Approximationsalgorithmus gibt. 3. Ein PTAS heißt volles Polynomzeit-Approximationsschema (fully polynomial time approximation scheme, kurz: FPTAS), falls die Laufzeit des e-Approximationsalgorithmus polynomiell sowohl bezüglich der Eingabegröße \x\ als auch bezüglich ^ ist. Beispiel 5.4. Für Einzelheiten siehe z.B. das Buch von Papadimitriou [23]. 1. Gemäß Kapitel 1 (vgl. die Faktor-2-Approximation aus Lemma 1.3) besitzt das Vertex Cover Problem einen ^-Approximationsalgorithmus. 2. Bin Packing: Gegeben: ai,..., aN, C, B G N \ {0}. Frage: Können die Zahlen a±,... in B Teilmengen so unterteilt werden, daß für jede die Summe ihrer Elemente höchstens C ist? Dieses Problem ist iVP-vollständig. Es besitzt ein PTAS, nicht jedoch eine FPTAS (es sei denn P = NP). Die Laufzeit ist n°^/e\ 3. Knapsack: Gegeben: si,..., s^, vi, ■ ■ ■, vn, W, K G N \ {0}. Frage: 3 T C {1,..., N}, so daß J2ier si < w und E^t vi ^ K? Dieses Problem ist ebenso iVP-vollständig. Knapsack besitzt jedoch ein FPTAS — der Algorithmus hat Laufzeit O(^). Folgendes, einfaches Ergebnis stellt eine wichtige Beziehung zwischen vollen Polynomzeitschemata (FPTAS) und der parametrisierten Klasse FPT her: Satz 5.5. Falls ein NP -Optimierungsproblem ein FPTAS besitzt, dann ist die parametrisierte Version des Problems in FPT. Beweis. Sei Q = (Iq, Sq, /q, optq) ein NP-Optimierungsproblem mit einem FPTAS. Wir beschränken uns in den nachfolgenden Betrachtungen auf Maximie-rungsprobleme, d.h. auf den Fall optq = max; der Beweis für den Minimie-rungsfall wird analog geführt. Sei weiter die parametrisierte Version von Q: Gegeben x G Iq und k G N; existiert y G Sq(x) mit fg(x,y) > kl 54 Wir wählen e = Da Q ein FPTAS besitzt, gibt es also einen Algorithmus mit polynomieller Laufzeit in der Eingabegröße n = \x\ und ^ = 2k, der für Eingabe x G Iq ein y £ Sq(x) ausgibt mit maxQ(x) - fQ(x,y) < = J_ maxQ(x) ~~ 2fc Arithmetische Umformung ergibt maxQ(x) ~~ 2fc 2fc Im Falle maxQ(x) > k folgt hiermit Jq(x, y) > k — ^. Da Jq(x, y) ganzzahlig ist, folgt somit auch fq(x,y) > fc. Wegen der Beziehung fq(x,y) < maxQ(x) folgt im Fall maxQ(x) < k erst recht fq{x,y) < k. Somit ergibt sich mit der Wahl von e = ^ ein parametrisierter Algorithmus, der zeigt, daß das parametrisierte Problem in FPT liegt. □ Wir schließen diesem Satz zwei wichtige Bemerkungen an. Bemerkung 5.6. 1. Der im Beweis zu Satz 5.5 beschriebene Algorithmus hat eine Laufzeit, die polynomiell sowohl in n = \x\ als auch 2k ist, also durch ein Polynom p{n, k) in zwei Variablen beschrieben werden kann. Die Definition von FPT (Definition 3.7) erlaubt aber sogar Laufzeiten der Form f(k) ■ — sie müssen also nicht polynomiell in k sein. Demzufolge könnte man in Satz 5.5 die Forderung nach einem FPTAS ersetzen durch die Forderung nach einem PTAS mit der zusätzlichen Eigenschaft, daß es eine Konstante c unabhängig von e gibt, so daß der e-Approximationsalgorithmus für festes e > 0 in Zeit 0(nc) läuft. 2. Die Umkehrung von Satz 5.5 (d.h. die Implikation „Nicht FPT kein FPTAS") liefert die interessantere Aussage: Läßt sich für ein para-metrisiertes Problem „zeigen", daß wenn es („wahrscheinlich") nicht in FPT liegt, so existiert (wahrscheinlich) auch kein FPTAS für das zugehörige Optimierungsproblem. Mehr dazu im nächsten Kapitel. Abschließend sei noch bemerkt, daß sich für bestimmte, „syntaktisch zu definierende" NP-Optimierungsprobleme zeigen läßt, daß ihre parametri-sierten Versionen in FPT liegen. Genauer heißt das, daß alle Probleme aus der sogenannten Maximierungsklasse MAXSNP und der Minimierungsklas-se MLNF+IIi(/i), h > 2, in FPT sind [7]. Ein Beispielproblem aus MAXSNP ist MaxSat, eines aus MINF+LIi(/i) ist Vertex Cover. Das Problem MaxSat 55 ist sogar MAXSNP-vollständig. Für derartige Probleme ist z.B. bekannt, daß sie sich bis auf einen bestimmten konstanten Faktor approximieren lassen (es existiert also ein e-Approximationsalgorithmus mit e < 1), aber sie besitzen kein FPTAS, wenn nicht P = NP (vgl. [2]). Es sei angemerkt, daß mittels solchen allgemeinen Aussagen (wie Satz 5.5) in der Regel nicht die effizientesten parametrisierten Algorithmen erhalten werden können. 56 6 Parametrisierte Komplexitätstheorie Nicht für alle parametrisierten Probleme lassen sich FPT-Algorithmen angeben. Ein Beweis dieser Aussage ist jedoch jenseits der gegenwärtigen Möglichkeiten der Komplexitätstheorie. Allerdings hilft auch hier (wie bei der „klassischen Komplexitätstheorie" mit der P versus NP Problematik) der Ubergang von „absoluter" zu „relativer" Komplexität. Mithilfe von Begriffen wie Reduktion und Vollständigkeit lassen sich „vollständige Probleme" definieren, so daß viele Indizien dagegen sprechen, daß diese Probleme in FPT liegen. Beispiele solcher Probleme sind u.a. Independent Set und Dominating Set. Im folgenden wollen wir die notwendigen Begriffe und Formalismen entwickeln, die zu einer solchen Theorie „hartnäckiger" parametrisierter Probleme führen. Der Begriff der Reduktion ist dabei das Herzstück. Es sei angemerkt, daß wir hier natürlich nur eine stark verkürzte und vereinfachte Darstellung der Ergebnisse geben können. 6.1 Parametrisierte Reduktion Um parametrisierte Probleme sinnvoll klassifizieren zu können, benötigen wir den Begriff der Reduktion. Dieser erweist sich als technisch schwieriger (da „feiner") als der in der klassischen Komplexitätstheorie übliche Reduktionsbegriff. Nachfolgend geben wir die wohl wichtigste Definition im Rahmen der parametrisierten Komplexitätstheorie. Definition 6.1. Seien L und L' zwei parametrisierte Probleme über S. Wir sagen, daß es eine parametrisierte Reduktion von L auf V gibt, wenn folgendes erfüllt ist: Es gibt Funktionen k i—> k! und k i—> k" auf N und eine Funktion (x, k) i—> x' von S* x N nach S* derart, daß 1. (x, k) i—> x' ist in Zeit k"\x\°^ berechenbar. 2. (x, k) G L gdw. (x', k1) G V. Beachte, daß in obiger Definition gefordert wird, daß weder k! noch k" vom Eingabewort x abhängen. Lediglich x' darf von k und x abhängen. Außerdem sei darauf hingewiesen, daß es auch noch die feineren Konzepte der streng uniformen, uniformen und nicht-uniformen parametrisierten Reduktion gibt. Diese sind für uns allerdings hier ohne Belang. Der Begriff der parametrisierten Reduktion soll an folgendem Beispiel ausführlich erläutert werden. 57 Beispiel 6.2. 1) Wir beschäftigen uns zunächst mit folgenden beiden Problemen: Weighted CNF Sat: Gegeben: Aussagenlogische Formel F in konjunktiver Normalform und ein Parameter k G N. Frage: Existiert eine erfüllende Belegung vom Gewicht k, d.h. eine Belegung, bei der genau k Variablen mit „wahr" belegt werden? Analog hierzu definiert man Weighted 3CNF Sat. Dabei darf jede Klausel aus höchstens 3 Literalen bestehen. Weighted Binary Integer Programming: Gegeben: Eine Matrix A und ein Vektor b mit Einträgen aus {0,1} und ein Parameter k G^N. Frage: Hat A • ~x > b einen Lösungsvektor über {0,1}, der aus genau k Einsen besteht (dabei ist „ > " komponentenweise zu verstehen) ? a) Um in der klassischen Komplexitätstheorie die NP-Vollständigkeit von 3CNF Sat (kurz: 3Sat) zu zeigen, reduziert man Sat auf 3Sat. Die Kernidee ist dabei wie folgt: Ersetze jeweils eine Klausel der Form {Ii V ... V lm) durch einen Ausdruck der Form (h yl2y zi) A(liV/3Vz2)A...A (zm_3 V Zm_i V lm). (2) Hierbei bezeichnen z±,..., zm_3 jeweils zusätzliche, neu eingeführte Variablen, die in der bisherigen Formel nicht vorkamen, und Ii,..., lm sind Variablen, oder negierte Variablen, sprich Literale. Es ist leicht nachzuprüfen, daß die solchermaßen entstehende 3CNF-Formel genau dann erfüllbar ist, wenn es die ursprüngliche CNF-Formel war; die Formeln sind also — wenn auch nicht „logisch äquivalent" — „erfüllbarkeitsäquivalent". Diese Reduktion von Sat auf 3Sat ergibt aber keine parametri-sierte Reduktion: Nehmen wir an, die ursprüngliche Sat-Formel hätte eine erfüllende Belegung mit Gewicht k, welche genau ein Literal lj in der Klausel {Ii V ... V lm) wahr macht. Um aber nun den Ausdruck (2) zu erfüllen, muß man alle Variablen zi,..., Zj-2 mit „wahr" belegen. Das bedeutet aber, daß sich das Gewicht der erfüllenden Belegung ändert, genauer gesagt, um j — 2 für diese Klausel größer wird. Entgegen Definition 6.1 hinge damit der Wert des „neuen" Parameters nicht nur vom „alten" ab, sondern auch von der Struktur der alten Formel (Klauselgrößen, ...). Also handelt es sich um keine parametrisierte Reduktion. In der Tat hätte es schwerwiegende Konsequenzen (Zusammenbruch der noch einzuführenden „W-Hierarchie" von parametri- 58 sierten Komplexitätsklassen), gäbe es eine parametrisierte Reduktion von Weighted CNF Sat auf Weighted 3CNF Sat. Deshalb gilt die Existenz einer solchen parametrisierten Reduktion als unwahrscheinlich, ja der Nachweis einer solchen käme einer Sensation gleich. b) Eine aussagenlogische Formel wird als monoton bezeichnet, falls sie keine Negationssymbole beinhaltet. Damit erhält man in natürlicher Weise das Weigthed Monotone CNF Sat Problem. Wir beschreiben nun eine parametrisierte Reduktion von Weighted Monotone CNF Sat auf Weighted Binary Integer Programming: Gegeben sei die CNF-Formel F = C\ A ... A Cp, wobei C±,..., Cp Klauseln sind, die aus den Variablen x±,... ,xm bestehen. Definiere die Binärmatrix A = (ajj)i b hat einen Lösungsvektor ~x vom Gewicht k F hat eine erfüllende Belegung vom Gewicht k. Diese Reduktion erfüllt also die Forderungen von Definition 6.1, insbesondere, da sie auch in Zeit ji7!0^-* durchgeführt werden kann. 2) Wir betrachten nun die schon bekannten (vgl. Abschnitt 2.2.1) parametrisierten Versionen der Graphprobleme Vertex Cover, Independent Set und Clique. Es gelten folgende Beziehungen: i) Ein Graph G = (V, E) hat eine Independent Set / der Größe k, genau dann wenn die Menge V — I ein Vertex Cover der Größe n — k ist (wobei n := \ V\). ii) Ein Graph G = (V, E) hat ein Independent Set der Größe k, genau dann wenn der Komplementgraph G = (V, E) (d.i. der Graph, bei welchem eine Kante {u, v} existiert, genau dann wenn {u, v} keine Kante von G ist) eine Clique (d.h. einen vollständigen Teilgraph) der Größe k besitzt. Die zu i) gehörige Reduktion ist keine parametrisierte Reduktion, da der „alte" Parameter k durch den „neuen" k' = n — k ersetzt wird, welcher also im Widerspruch zu Definition 6.1 auch von der Eingabe selbst und nicht nur vom Parameter k abhängt. 59 Hingegen erfüllt ii) die Bedingungen von Definition 6.1, es handelt sich also um eine parametrisierte Reduktion. Clique und Independent Set sind damit auch im parametrisierten Sinne „gleich schwer". Bemerkung 6.3. • Es ist eher die Ausnahme als die Regel, daß „klassische Reduktionen" auch als parametrisierte Reduktionen taugen; letztere erfordern in der Regel größere Sorgfalt und mehr technischen Aufwand. • Sollte sich „erweisen", daß irgendein parametrisiertes Problem nicht in FPT liegt, so „darf" es keine parametrisierte Reduktion von diesem Problem auf z.B. Vertex Cover oder irgendein anderes Problem in FPT geben. 6.2 Parametrisierte Komplexitätsklassen Die NP-Vollständigkeit des Erfüllbarkeitsproblems für aussagenlogische Formeln in konjunktiver Normalform (Sat) wurde dadurch gezeigt, daß quasi die Berechnung einer nichtdeterministischen Turingmaschine mit polynomieller Laufzeit durch eine aussagenlogische Formel beschrieben wurde. Der Glauben an die Hartnäckigkeit von NP-vollständigen Problemen wie Sat, Vertex Cover oder Clique beruht insbesondere auch darauf, daß es eben als recht unwahrscheinlich gilt, daß man eine nichtdeterministischen Turingmaschine mit polynomieller Laufzeit durch eine deterministische Turingmaschine mit polynomieller Laufzeit simulieren kann. Wir haben demgemäß folgendes, einfaches iVP-vollständiges Problem: Turing Machine Acceptance: Gegeben: Eine nichtdeterministische Turingmaschine M, ein Eingabewort x für M und eine unär (d.h. über einem einelementigen Alphabet) kodierte Zahl m. Frage: Besitzt M auf Eingabe x einen akzeptierenden Berechnungspfad der Länge < ml In der „parametrisierten Welt" gibt es nun folgendes Analogon: Short Turing Machine Acceptance: Gegeben: Eine nichtdeterministische Turingmaschine M, ein Eingabewort x für M und ein Parameter k G N. Frage: Besitzt M auf Eingabe x einen akzeptierenden Berechnungspfad der Länge < kl Ähnlich wie sich philosophisch über die Hartnäckigkeit von Turing Machine Acceptance diskutieren läßt, ist das von einem „parametrisierten Blickwinkel" aus auch für Short Turing Machine Acceptance möglich. Es besteht 60 wenig Hoffnung, daß Short Turing Machine Acceptance einen effizienten pa-rametrisierten Algorithmus besitzt. D.h., daß dieses Problem wohl nicht in FPTliegt. (Versuche, einen Algorithmus mit Laufzeit f{k)-n°^ anzugeben! Gelänge dies, so wäre man reif für eine Sensation.) Demgemäß taugt Short Turing Machine Acceptance als Kernproblem zur Betrachtung einer Klasse „harter" parametrisierter Probleme (mithilfe des Reduktionskonzepts). Leider ist das Studium „parametrisierter Hartnäckigkeit" technisch komplizierter als das vergleichbare Konzept in der klassischen Komplexitätstheorie. Demzufolge sind die zugehörigen Komplexitätsklassen auch aufwendiger zu definieren. Der Grundgedanke bei der Einführung parametrisierter Komplexitätsklassen „überhalb" von FPT ist die Klassifikation von Problemen gemäß ihrer „logischen Tiefe". Im Gegensatz zur klassischen Komplexitätstheorie werden diese Komplexitätsklassen also nicht über entsprechende Maschinenmodelle definiert. Vielmehr benutzen wir folgendes Konzept: Definition 6.4. 1. Ein Boolesches Schaltnetz C ist ein gerichter, azyklischer Graph, bei dem die Knoten als Gatter bezeichnet werden. Außerdem wird jedem Gatter eine aussagenlogische Funktion (Und, Oder, Negation) oder eine Eingabevariable zugeordnet. Schließlich gibt es noch ein ausgezeichnetes Gatter, das die Ausgabe des Schaltnetzes bestimmt. 2. Kleine Gatter von C sind Gatter Und, Oder, Negation, wobei der Eingangsgrad durch 2 beschränkt ist. Große Gatter von C sind Gatter Und, Oder, Negation mit Eingangsgrad größer als 2.11 3. Die Tiefe von C ist die maximale Anzahl von Gattern auf einem Eingabe-Ausgabe-Pfad. Die Weft12 von C ist die maximale Anzahl von großen Gattern auf einem Eingabe-Ausgabe-Pfad in C. Beispiel 6.5. Abbildung 8 zeigt ein Weft 2, Tiefe 4 Schaltnetz. Definition 6.6. Sei T = {C±, C2, C3,...} eine Familie von Schaltnetzen, wobei d genau i Eingabevariablen besitze. Wir definieren Ljp := { < Ci,k >| Ci hat eine erfüllende Belegung mit Gewicht k }. Ar(t,/i) ist dann Ljp eingeschränkt auf Weft t und Tiefe h Schaltnetze. 11Die Festlegung auf die Konstante 2 als Trennwert zwischen kleinen und großen Gattern ist liier rein willkürlich. Es hätte eine beliebige andere Konstante > 2 sein können. Dies kommt z.B. auch später in der Definition 6.10 zum Tragen. 12Von Englisch „Schußfaden" (bei einem Webstuhl). 61 X\ X2 X3 X4 X§ V Ausgabe Abbildung 8: Schaltnetz der Tiefe 5 und Weft 2. Beispiel 6.7. Weighted CNF Sat gehört zu L^(2)2); Weighted 2CNF Sat gehört zu Ljr^^y Definition 6.8. Ein parametrisiertes Problem L gehört zur Komplexitätsklasse W[t] genau dann, wenn es mittels einer parametrisierten Reduktion auf die Sprache einer Schaltnetzfamilie L^t^ zurückgeführt werden kann, so daß die Tiefe h konstant ist. Beispiel 6.9. 1. Independent Set und Clique sind in W[l]: Beobachtung: Ein Graph G = (V, E) mit V = {1, 2,...} hat eine Independent Set der Größe k. 44> 62 Nachfolgende Formel hat eine erfüllende Belegung vom Gewicht k: A faVxj). (3) Beachte, daß eine Independent Set genau die Eigenschaft hat, daß von je zwei benachbarten Knoten i,j £ V (d.h. {i,j} G E) höchstens einer in der Independent Set liegen kann. Dies entspricht gerade der aussagenlogischen Formel X{ A Xj = ~xi V ~xj. Leicht zu überprüfen ist, daß die Abbildung von Independent Set auf das beschriebene Erfüllbarkeitsproblem mit einer parametrisier-ten Reduktion gemäß Definition 6.1 geschehen kann. Da obige Formel (3) in 2CNF ist, somit insbesondere auch durch ein Weft 1, Tiefe 2 Schaltnetz beschrieben werden kann (d.h. also auf £^-(1,2) zurückgeführt werden kann), folgt mit Definition 6.8, daß Independent Set in W[l] ist. Mit der parametrisierten Reduktion aus Beispiel 6.2.2.(ii) (Ubergang auf den Komplementgraph) folgt auch, daß Clique in W[l] liegt. 2. Dominating Set ist in W[2]: Beobachtung: Ein Graph G = (V, E) mit V = {1, 2,...} hat eine „Dominating Set" der Größe k. Nachfolgende Formel hat eine erfüllende Belegung vom Gewicht k (dabei bezeichne N(i) die Menge der Nachbarknoten des Knotens i): f\ V {xi,xh,... ,Xj3.). (4) iev N(i)={h,...,ij} Dies zeigt, daß sich Dominating Set durch eine parametrisierte Reduktion auf das in (4) beschriebene, gewichtete Erfüllbarkeitsproblem zurückführen läßt. Dieses wiederum ist durch Schaltnetze der Familie Ljp(2j2) beschreibbar, sprich Dominating Set liegt in W[2]. Beachte, daß es — im Gegensatz zu Formel (3) — bei der Formel (4) zweier aufeinanderfolgender Gatter mit unbeschränktem Eingangsgrad bedurfte. In diesem Sinne haben also Clique und Dominating Set verschiedene logische Tiefe. Gemäß nachfolgender Theorie käme es einer Sensation gleich, könnte man Dominating Set als ein Weighted gCNF Sat Problem (mit konstantem q) ausdrücken. 63 6.3 Vollständige Probleme und die W-Hierarchie Zur Definition von W[t] betrachteten wir folgende Probleme: Weighted Weft t Depth h Circuit Satisfiability (WCS(t,/i)): Gegeben: Ein Schaltnetz C mit Weft t und Tiefe h und ein k G N. Frage: Hat C eine erfüllende Belegung mit Gewicht kl Weighted 3CNF Sat ist z.B. ein Spezialfall von WCS(1,2). Uns interessiert nachfolgend unter anderem die Frage, wie groß die Konstante h in der Definition von W[t] und speziell W[l] sein muß. Definition 6.10. Unter W[l, s] verstehen wir die Teilmenge von W[l], welche mittels einer parametrisierten Reduktion auf die Sprache Lp(s) der Familie J-{s) von s-normalisierten Schaltnetzen der Weft 1 und Tiefe 2 reduziert werden können. Dabei bedeutet s-normalisiert, daß sich in Tiefe 1 nur OüER-Gatter mit Eingangsgrad höchstens s befinden und in Tiefe 2 ein einziges, großes UND-Gatter ist. Mit großem technischen Aufwand läßt sich folgendes Zwischenergebnis beweisen. Wir benötigen zur Formulierung des Ergebnisses noch den Begriff der „Antimonotonie": Definition 6.11. Antimonotone W[l,s] ist die Einschränkung von W[l, s] auf Schaltnetze, bei welchen alle Eingabevariablen negiert in das Schaltnetz gegeben werden, im eigentlichen Schaltnetz dann aber keine Negationsgatter mehr auftauchen. Damit erhalten wir das angekündigte Resultat (vgl. [12, Lemma 10.5, Theorem 10.6]): Mitteilung 6.12. Es gelten folgende Aussagen: i- w[i] = \J2=1w[i,8]. 2. W[l, s] = AntimonontoneW[l, s] für s > 2. Mithilfe obiger Mitteilung läßt sich zeigen, daß die Schaltnetze, welche wir zur Beschreibung von W[l] tatsächlich benötigen, von sehr spezieller Gestalt sein können (vgl.[12, Theorem 10.7.]). Dieses Ergebnis wird zur Beschreibung W[l]-vollständiger Probleme von großem Nutzen sein. Satz 6.13. Es gilt W[l] = W[l,2]. 64 Beweis. Die Inklusion „5" ist nach Definition 6.10 klar. Für die umgekehrte Inklusion genügt dank Mitteilung 6.12 der Nachweis der Inklusion Antimonotone W'[1, s] C W[l,2], für alle s > 2. Sei also ein Antimonotone W[l, s]-Schaltnetz C gegeben. Wir werden hierzu einen Ausdruck C in 2CNF konstruieren, so daß folgendes gilt: C hat eine erfüllende Belegung vom Gewicht k C hat eine erfüllende Belegung vom Gewicht k' := k2k + J2t=2 (*)• Zunächst zur Konstruktion von C aus C: Seien x±,..., xn die Eingabevariablen von C. Wir betrachten alle Teilmengen der Größen 2 bis s der Eingabevariablenmenge. Bezeichne diese Teilmengen mit A±,..., Ap. Die Eingaben eines OüER-Gatters von C entsprechen also genau einem Ai, 1 < i < p. Zu jedem Ai korrespondiere in C eine neue Variable V{. Falls V{ den Wert „wahr" hat, so bedeutet dies also, daß alle Variablen, deren negierte Werte Eingänge des zu Ai gehörenden OüER-Gastters sind, ebenso „wahr" sind. Deshalb wird in der Konstruktion von C das zu Ai gehörende OüER-Gatter durch Vi ersetzt. Desweiteren werden für jede Eingabevariable Xj genau 2k neue Eingabevariablen („Kopien") Xjß,... ,Xj£k-i eingeführt. Die Konstruktion von C aus C sieht nun wie folgt aus: Zunächst werden alle OüER-Gatter durch die entsprechenden Negationen von Vis ersetzt. Desweiteren werden folgende weiteren Bestandteile jeweils per Und-Verknüpfung angehängt (diese dienen dazu, notwendige Nebenbedingungen und die Korrektheit der Behauptung zu garantieren): a) Xj:r a^r+i( mod 2fe) für j = 1,..., n und r = 0,..., 2k — 1. b) Vi< Vi falls Ai C A41. c) Vi Xjß falls Xj £ Ai. Informell ausgedrückt implizieren diese Bedingungen, daß eine Belegung von C nur dann erfüllend sein kann, wenn folgendes gilt: Ist ein „wahr", so müssen auch alle Vi, welche zu Teilmengen Ai C A41 gehören „wahr" sein (Bed. b)). Darüber hinaus verlangen Bedingung c) und a), daß in diesem Fall auch alle „ Kopien" Xjfl,... ,Xj£k-i von Variablen Xj, welche in diesen Teilmengen Ai C A# auftauchen, „wahr" sein müssen. 65 Beachte, daß die obigen Implikationen jeweils durch eine zweistellige Oder-Verknüpfung ausgedrückt werden können. Dies beschließt die Konstruktion von C. Die Größe von C im Vergleich zu C wächst größenordnungsmäßig nur um den Faktor 2k, bzw. additiv um Yli=2 (?) = 0{ns) für konstantes s. Die Konstruktion ist daher durch eine parametrisierte Reduktion zu bewältigen. Zur Korrektheit der Konstruktion und damit der Behauptung: i) Annahme: C hat eine erfüllende Belegung vom Gewicht k, die genau die Variablen Xj1,..., Xjk mit „wahr" belegt. Dann setzte die 2k ■ k Variablen XjltQ,..., Xji^2k_i,..., Xjk,o, ■ ■ ■, xjk)2k-i auf „wahr" und entsprechend alle Variablen v^, die zu einem der Ai gehören, welche eine Teilmenge der Variablen in Xj1,..., Xjk bilden. Davon gibt es X]i=2 (?) viele. Nach Konstruktion von C gibt das eine erfüllende Belegung vom Gewicht k2k + Y!l=2 (?) = k'- ii) Umkehrannahme: C hat eine erfüllende Belegung vom Gewicht k' = k2k + 5^i=2 (?)• Bedingung a) besagt, daß für jedes j gilt: Xjtr = True für ein r g {1,..., 2k — 1} Xjj = True für alle l e {1,..., 2k - 1} . Diese Eigenschaft und die Tatsache, daß 2k > X]i=2 (?) garantieren, daß für eine erfüllende Belegung von C mit Gewicht k! genau k „Kopiemengen" (jede der Größe 2k) auf „wahr" gesetzt sind. Diese entsprechen einer Belegung von C mit Gewicht k (man identifiziere wiederum jede der „Kopiemengen" Xjß,... ,a^2fe-i aus C mit der Variablen Xj in C). Nach Konstruktion ist es leicht zu sehen, daß die so erhaltene Belegung von C erfüllend ist. Insbesondere stellen dabei die Bedingungen b) und c) sicher, daß die Belegung der Variablen V{ „kompatibel" mit den Belegungen der Kopiemengen sind. □ Mithilfe von Satz 6.13 lassen sich nun relativ einfach Vollständigkeitsbeweise für W[l] führen: Satz 6.14. Folgende Probleme sind W[l]-vollständig: • Independent Set. • Clique. 66 • Weighted qCNF Sat für konstantes q > 2. • Short Turing Machine Acceptance. Beweisskizze. Leicht sieht man (vgl. das Beispiel 6.9), daß Independent Set und Clique in W[l] sind. Es verbleibt also die „Härte" nachzuweisen. Mit Satz 6.13 und Mitteilung 6.12 müssen wir hierzu zeigen, daß wir das gewichtete Erfüllbarkeitsproblem für antimonotone 2CNF-Formeln mittels einer parametrisierten Reduktion auf z.B. Independent Set (der Beweis für Clique läuft analog) zurückführen können. Sei dazu F eine antimonotone Formel in 2CNF. Wir konstruieren einen Graph Gf, bei welchem jeder Variablen in F ein Knoten in Gf und jeder Klausel eine Kante entspricht. Dann ist leicht zu sehen (man mache sich dies an einem einfachen Beispiel klar!): F hat eine erfüllende Belegung vom Gewicht k. Gf hat eine Independent Set der Größe k. Die Vollständigkeit von Weighted gCNF Sat ergibt sich direkt aus der Konstruktion in Satz 6.13. Für die Vollständigkeit von Short Turing Machine Acceptance verweisen wir auf [12, S.245/250]. Die Idee besteht darin, Clique auf Short Turing Machine Acceptance (parametrisiert) zu reduzieren. Wichtig hierbei ist, daß die zu konstruierende TM ein unbeschränktes Eingabealphabet haben darf. Short Turing Machine Acceptance mit beschränktem (d.h. konstant großem) Eingabealphabet liegt in FPT. □ Abschließend wollen wir darauf hinweisen, daß es wohl Probleme gibt, welche zwischen P und NP liegen (also nicht iVP-vollständig sind, aber auch nicht in P liegen), aber dennoch W[l]-vollständig sind. Dies gilt etwa für die Berechnung der sog. Vapnik-Chervonenkis-Dimension, einem Problem aus der Lerntheorie. Dies soll zeigen, daß die klassische Komplexitätstheorie und die parametrisierte Komplexitätstheorie in gewisser Hinsicht „orthogonal" zueinander liegen: Im klassischen Sinne ist Vertex Cover „schwerer" als die Bestimmung der Vapnik-Chervonenkis-Dimension (da Vertex Cover NP-vollständig ist), im parametrisierten Sinn jedoch „leichter" (da in FPT). Abschließend soll noch kurz die W-Hierarchie vorgestellt werden, welche parametrisierte Probleme — wie bereits erwähnt — gemäß ihrer logischen Tiefe klassifiziert: Definition 6.15. Die W-Hierarchie ist die Vereinigung aller parametrisierten Komplexitätsklassen W[t], t > 1, zusammen mit den zwei zusätzlichen 67 Klassen W[Sat] und W[P], wobei diese analog zu den WftJ-Klassen definiert sind, nur daß bei W[P] keine Beschränkung der Schaltnetztiefe besteht und bei W[Sat] aussagenlogische Formeln polynomieller Größe (anstelle von Schaltnetzen polynomieller Größe wie bei W[P]) verwendet werden. Somit haben wir FPT C W[l] C W[2] C ... C W[Sat] C W[P]. Es wird vermutet, daß obige Inklusionen alle echt sind. Es läßt sich im übrigen einfach zeigen, daß mit P = NP bereits W[P] =FPT gelten würde. Die Gültigkeit der Umkehrung dieser Aussage ist nicht bekannt. Zur Angabe vollständiger Probleme für die W-Hierarchie brauchen wir noch: Definition 6.16. Eine aussagenlogische Formel heißt t-normalisiert, falls sie von der Form „Produkt-von-Summen-von-Produkten-von-..." von Literalen ist mit t — 1 Alternierungen. Beispiel 6.17. CNF ist 2-normalisiert. Mitteilung 6.18. Weighted t-normalized Sat ist W\t\-vollständig für t > 2. Mitteilung 6.19. Dominating Set ist W[2]-vollständig. Beispiel 6.20. Abschließend wollen wir ein Beispiel für die verschiedenen Parametrisierungsmöglichkeiten und damit verbunden die verschiedenen pa-rametrisierten Komplexitäten eines Problems geben. Longest Common Subsequence Problem (LCS) Gegeben: k Zeichenketten X±,..., Xk über einem Alphabet £ und m G N. Frage: Existiert X G S* mit \X\ > m, so daß X Teilsequenz(Beachte, daß hier nicht Teilzeichenkette gemeint ist.) aller Xi ist? LCS spielt eine wichtige Rolle in der algorithmischen Biologie. Es läßt sich auf verschiedene Weisen „parametrisieren": LCS1: Nur k als Parameter. LCS2: Nur m als Parameter. LCS3: k und m als Parameter. Der gegenwärtige Kenntnisstand über die parametrisierte Komplexität dieser Varianten läßt sich folgender Tabelle entnehmen: 68 Problem Parameter £ unbeschränkt £ beschränkt LCS1 k W[£]-hart für alle t > 1 W[l]-hart LCS2 m W [2]-hart FPT LCS3 k, m W [ 1 ] - vollst ändig FPT Es ist also immer sorgfältig zu untersuchen, welche Parametrisierung für das gegebene Problem (anwendungsbedingt) sinnvoll ist. 6.4 Strukturelle Ergebnisse In diesem Abschnitt sollen noch kurz Indizien aufgezeigt werden, die für die „Echtheit" der W-Hierarchie und insbesondere die Hartnäckigkeit von W[l]-harten Problemen sprechen. Die fundamentale Hypothese der parame-trisierten Komplexitätstheorie ist die Ungleichheit W[l] ^ FPT. Eine weitere Hypothese ist beispielsweise W[l] ^ W[2}. Da es beim gegenwärtigen Stand der Forschung als recht hoffnungslos gilt, eine Aussage wie W[l] ^ FPT zeigen zu können, geht man über zu „relativen Aussagen". Würde also z.B. die Annahme W[l] = FPT eine Aussage (in der klassischen Komplexitätstheorie) implizieren, welche als sehr unwahrscheinlich oder überraschend gilt? In diese Richtung stoßen die nachfolgend vorgestellten Sätze, die ohne Beweis nur als Mitteilung gegeben werden. Leider ist keine derart starke (relative) Aussage wie etwa W[P] = FPT^P = NP bekannt. Deshalb müssen wir zu „schwächeren Aussagen" übergehen, wozu das Konzept des „beschränkten Nichtdeterminismus" benötigt wird. Definition 6.21. 1. NP[f(n)\ bezeichne die Klasse von Entscheidungsproblemen, die in polynomieller Zeit von einer nichtdeterministischen Turingmaschine gelöst werden können, welche nur f(n) viele nichtdeterministische Schritte erlaubt. 2. SUBEXPTIME [f(n)\ bezeichne die Klasse von Sprachen, die von einer deterministischen Turingmaschine in Zeit nP^ ■ 29^ für ein g in o(f(n)) akzeptiert werden können. Mitteilung 6.22. Folgende Aussagen sind äquivalent: 69 (i) W[P] =FPT. (ii) Es gilt NP[f(n)] C SUBEXPTIME [f(n)] für alle in Polynomzeit berechenbaren Funktionen f(n) mit f(n) > logn. Beachte, daß obige Aussage (ii) anschaulich bedeutet, daß für jedes NP[f(n)]-Problem ein deterministischer Algorithmus gefunden werden kann, welcher mit weniger Schritten auskommt, als der naive Ansatz, welcher alle exponen-tiell vielen Möglichkeiten durchprobiert. Dies gilt in der klassischen Komplexitätstheorie als sehr unwahrscheinlich. Mitteilung 6.23. W[l] =FPT => 3CNF Sat kann in Zeit 2°^ gelöst werden. Auch diese Folgerung gilt in der klassischen Komplexitätstheorie als sehr unwahrscheinlich. Der bislang beste Algorithmus für 3CNF Sat hat Laufzeit « 1.5n = 2°(n) ^ 2°(n) (siehe [17, 26]). 70 7 Blick zurück und nach vorn Das Studium parametrisierter Algorithmen und ihrer Komplexität ist ein junges und vielversprechendes Forschungsbgebiet mit unstrittiger praktischer Relevanz. Neue Techniken (Reduktion auf den Problemkern, tiefenbeschränkter Suchbaum, Farbkodierungen etc.) sind die Grundlage für effiziente parametrisierte Algorithmen. Ähnlich wie in der klassischen Komplexitätstheorie P und NP, so stehen sich in der parametrisierten Komplexitätstheorie FPT und W[l] (-Härte) als gutartige und bösartige Probleme gegenüber. Leider ist bislang noch nicht der Beleg erbracht, daß die Mehrzahl der Probleme in FPT wirklich effiziente, praxistaugliche Algorithmen besitzen. Dies muß Gegenstand zukünftiger Forschung sein. Zusammenfassend lassen sich folgende Themen als Höhepunkte des behandelten Stoffs betrachten. • Vertex Cover und seine effizienten parametrisierten Algorithmen. • parametrisierte Algorithmen im Vergleich mit anderen Ansätzen zur Handhabung kombinatorisch schwieriger Probleme. • Fixed parameter tractable Probleme. • Reduktion auf den Problemkern. • Suchbäume beschränkter Tiefe. • Farbkodierungen und Hashing. • Approximation und parametrisierte Algorithmen. • parametrisierte Reduktion. • W-Hierarchie und vollständige Probleme. Die Zukunft des Gebiets der parametrisierten Algorithmen hängt eng mit ihrer Bewährung in der Praxis zusammen. Bislang wurden noch relativ wenige der Algorithmen implementiert. Außerdem ist von entscheidender Bedeutung, ob FPT wirklich auch als Konzept für effiziente parametrisierte Algorithmen tragfähig ist. Letzlich entscheidet sich das Schicksal parametrisierter Algorithmen wohl auch im direkten Vergleich mit in der Praxis eingesetzten heuristischen Verfahren und den Bezügen zwischen beiden Ansätzen, ggf. auch ihrer Kombinierbarkeit. Viel ist noch zu tun — auch im Rahmen von Studien- und Diplomarbeiten, die sowohl theoretisch als auch praktisch ausgerichtet sein können. 71 Literatur [1] N. Alon, R. Yuster, and U. Zwick. Color-coding. Journal of the ACM, 42(4):844-856, 1995. [2] S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and hardness of approximation problems. In Proceedings of the 33d IEEE Symposium on Foundations of Computer Science, pages 14-23, 1992. [3] R. Balasubramanian, M. R. Fellows, and V. Raman. An improved fixed parameter algorithm for vertex cover. Information Processing Letters, 65(3):163-168, 1998. [4] R. Bar-Yehuda and S. Even. A local-ratio theorem for approximating the weighted vertex cover problem. Annals of Disc. Math., 25:27-46, 1985. [5] H. L. Bodlaender. A linear time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing, 25:1305-1317, 1996. [6] J. F. Buss and J. Goldsmith. Nondeterminism within P. SIAM Journal on Computing, 22(3):560-572, 1993. [7] L. Cai and J. Chen. On fixed-parameter tractability and approxima-bility of NP optimization problems. Journal of Computer and System Sciences, 54:465-474, 1997. [8] J. Chen, I. Kanj, and W. Jia. Vertex cover: Further observations and further improvements. To appear at 25th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'99), Ascona, Switzerland, June 1999. [9] T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms. The MIT Press, 1990. [10] B. Courcelle. The monadic second order theory of graphs I: Recognisable sets of finite graphs. Information and Computation, 85:12-75, 1990. [11] P. Crescenzi and V. Kann. How to find the best approximation results— a follow-up to Garey and Johnson. ACM SIGACT News, 29(4):90-97, 1998. [12] R. G. Downey and M. R. Fellows. Parameterized Complexity. Springer-Verlag, 1999. 72 [13] R. G. Downey, M. R. Fellows, and U. Stege. Parameterized complexity: A framework for systematically confronting computational intractability. DIM ACS Series in Discrete Mathematics and Theoretical Computer Science, 49, 1999. [14] R. C. Evans. Testing repairable RAMs and mostly good memories. In Proceedings of the IEEE Int. Test Conf., pages 49-55, 1981. [15] M. Garey and D. Johnson. Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman, San Francisco, 1979. [16] J. Hästad. Some optimal inapproximability results. In Proceedings of the 29th ACM Symposium on Theory of Computing, pages 1-10, 1997. [17] O. Kullmann. New methods for 3-SAT decison and worst-case analysis. Theoretical Computer Science, 223:1-72, 1999. [18] K. Mehlhorn. Graph algorithms and NP-completeness. Heidelberg: Springer, 1984. [19] B. Monien and E. Speckenmeyer. Ramsey numbers and an approximation algorithm for the vertex cover problem. Acta Informatica, 22:115— 123, 1985. [20] R. Niedermeier. Some prospects for efficent fixed parameter algorithms (invited paper). In B. Rovan, editor, Proceedings of the 25th Conference on Current Trends in Theory and Practice of Informatics (SOFSEM), number 1521 in Lecture Notes in Computer Science, pages 168-185. Springer-Verlag, 1998. [21] R. Niedermeier and P. Rossmanith. A general method to speed up fixed-parameter-tractable algorithms. Technical Report TUM-I9913, Institut für Informatik, Technische Universität München,Fed. Rep. of Germany, June 1999. Submitted to Information Processing Letters. [22] R. Niedermeier and P. Rossmanith. Upper bounds for Vertex Cover further improved. In C. Meinel and S. Tison, editors, Proceedings of the 16th Symposium on Theoretical Aspects of Computer Science, number 1563 in Lecture Notes in Computer Science, pages 561-570. Springer-Verlag, 1999. [23] C. H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994. [24] V. Raman. Parameterized complexity. In Proceedings of the 7th National Seminar on Theoretical Computer Science (Chennai, India), pages I 1 I 18, June 1997. 73 [25] J. M. Robson. Algorithms for maximum independent sets. J. Algorithms, 7:425-440, 1986. [26] I. Schiermeyer. Pure literal look ahead: An 0(1.497n) 3-Satisfiability algorithm. Technical Report 96-230, Universität Köln, 1996. [27] U. Stege and M. Fellows. An improved fixed-parameter-tractable algorithm for vertex cover. Technical Report 318, Department of Computer Science, ETH Zürich, April 1999. [28] M. Thorup. Structured programs have small tree-width and good register allocation. In R. Möhring, editor, Proceedings of the 23rd International Workshop on Graph-Theoretic Concepts in Computer Science, number 1335 in Lecture Notes in Computer Science, pages 318-332. Springer-Verlag, 1997. 74 Index Algorithmische Biologie, 5, 7, 14 Algorithmus Brute-force, 12, 26 genetischer, 10 parametrisierter, 7 randomisierter, 9, 34 Analyse Average Case, 8 Worst Case, 8 Approximation, 8 Approximationsalgorithmus, 6 e-Approximationsalgorithmus, 41 Baum-Automaten, 40 Baumweite, 14, 39 Baumzerlegung, 14 Weite, 14 Bin Packing, 42 Boolesches Schaltnetz, 49 Charakterisierung mittels Ausschlußmengen, 23 endliche, 23 Clique, 9, 18, 47, 50, 54 3CNF Sat, 58 DNA-Computer, 10 Dominating Set, 12, 17, 18, 51, 56 Dynamisches Programmieren, 33 Eingabeinstanzen, 41 erfüllbarkeitsäquivalent, 46 erwartete Laufzeit, 33 Explosion kombinatorische, 4, 10 Farbkodierung, 32 fixed parameter tractable, 19 nicht-uniform, 19 streng, 19 uniform, 19 forbidden set characterization, siehe Charakterisierung mittels Ausschlußmengen FPT, 19 FPTAS, 42 Gatter, 49 große, 49 kleine, 49 Gewicht, 46 Graph bipartiter, 23 chordaler, 26 planarer, 23, 37 Grapheneigenschaft, 22 vererbbare, 22 Graphminoren, 37 Graphminorensatz, 38 Hash-Funktionen fc-perfekte, 34 Hashing, 32, 34, 35 Heuristische Verfahren, 10 Hitting Set, 21, 27 2HS, 21 3HS, siehe Hitting Set Independent Set, 12, 18, 47, 50, 54 Künstliche Intelligenz, 10, 14 Kantenhinzufügungsproblem, 24 Kantenkontraktion, 37 Kantenlöschungsproblem, 23 Knapsack, 42 Knoten- und Kantenlöschungsproblem, 23 Knotenüberdeckungsproblem, siehe Vertex Cover Knotengrad, 28 Knotenlöschungsproblem, 23 Komplementgraph, 47 Kryptographie, 9 75 Lösungsschema, 36 LCS, siehe Longest Common Subsequence Problem Logik- und Datenbank-Probleme, 14 logisch äquivalent, 46 Longest Common Subsequence Problem, 56 Longest Cycle, 32 Longest Path, 32 Maximierungsklasse, 43 Maximierungsproblem, 41 MaxSat, 18, 43 MAXSNP, 43 MINF+IIi(/i), 43 Minimierungsklasse, 43 Minimierungsproblem, 41 Minimum Fill In, 26 Minor, 37 Minorenbildung abgeschlossen unter, 37 Multidimensional Matching, 35 Netzwerk-Probleme, 13 Neuronale Netze, 10 Node Cover, 5, siehe Vertex Cover t-normalisiert, 56 NP, 17 NP-hart, 4, 8, 18 NP-Optimierungsproblem, 41 NP-vollständig, 5, 8, 17, 32 NP[f(n)], 57 Obstruktionsmenge, 37 P, 17 Parameter, 4, 18 Parse-Baum, 40 Pattern Matching, 9 Pfad voll bunter, 33 n-Graph, 22 Pi- G r aphenmo difikationspr oblemLI.; j^-G r aphenmo difikationspr oblem, 23 Polynomzeit-Approximationsschema, 42 Problem parametrisiertes, 18 PTAS, 42 QBF, 18 Quantum-Computer, 10 Reduktion, 17, 45 parametrisierte, 45 Reduktionsfunktion, 17 Rekursionsformel, 28 Robotik, 14 Schaltnetz s-normalisiert, 52 Tiefe, 49 Weft, 49 Short NTM computation, 19 Short Turing Machine Acceptance, 54 SUBEXPTIME [/(n)], 57 Suchbaum tiefenbeschränkter, 7, 26 Teilgraph induzierter, 22 verbotener, 23 Teilsequenz, 56 Turing Machine Acceptance, 48 Vapnik- Chervonenkis- Dimension, 55 Verfahren heuristische, 6 Vertex Cover, 5, 9-11, 17, 18, 20, 28, 38, 47 Verzweigungsvektor, 28 Verzweigungszahl, 28 W-Hierarchie, 55 W[t], 50 76 W[P], 55 W[Sat], 55 WCS, 51 Weighted gCNF Sat, 19, 51, 54 Weighted t-normalized Sat, 56 Weighted 3CNF Sat, 46 Weighted CNF Sat, 46, 49 Weigthed Monotone CNF Sat, 47 Zielfunktion, 41