Wie man NP-schwere Probleme mit parametrisierten Algorithmen löst

Alle Überlegungen bis zu diesem Algorithmus führen zum Beispiel von Kernelisierung — eine der allgemeinen Techniken zur Erstellung parametrisierter Algorithmen. Kernelisation ist die Reduzierung der Größe eines Problems auf einen Wert, der durch eine Funktion des Parameters begrenzt wird. Das erhaltene Problem wird oft als Kern bezeichnet. So haben wir durch einfache Überlegungen zu den Graden der Knoten einen quadratischen Kern für das Problem des Vertex Cover erhalten, parametrisiert durch die Größe der Antwort. Es gibt auch andere Parameter, die für dieses Problem gewählt werden können (zum Beispiel Vertex Cover Above LP), aber wir werden genau über diesen Parameter sprechen.

Pace Challenge

Wettbewerb PACE Challenge (Die Herausforderung der parametrisierten Algorithmen und rechnerischen Experimente) entstand 2015, um eine Verbindung zwischen parametrisierten Algorithmen und den in der Praxis verwendeten Ansätzen zur Lösung von Rechenproblemen herzustellen. Die ersten drei Wettbewerbe waren dem Finden der Baumweite eines Graphen (Treewidth), dem Finden eines Steiner-Baums (Steiner Tree) und dem Finden eines Satzes von Knoten, der Zyklen schneidet (Feedback Vertex Set). In diesem Jahr war eine der Aufgaben, in denen man sein Können versuchen konnte, das oben beschriebene Problem des Vertex Cover.

Der Wettbewerb gewinnt von Jahr zu Jahr an Popularität. Wenn man den vorläufigen Daten Glauben schenken darf, haben in diesem Jahr alleine beim Wettbewerb zur Lösung des Vertex Cover-Problems 24 Teams teilgenommen. Es ist erwähnenswert, dass der Wettbewerb nicht nur einige Stunden oder sogar eine Woche dauert, sondern mehrere Monate. Die Teams haben die Möglichkeit, Fachliteratur zu studieren, ihre eigene originelle Idee zu entwickeln und diese umzusetzen. Im Grunde genommen stellt dieser Wettbewerb eine Forschungsarbeit dar. Die Ideen der effektivsten Lösungen und die Preisverleihung der Gewinner finden gemeinsam mit der Konferenz IPEC (International Symposium on Parameterized and Exact Computation) im Rahmen der größten jährlichen algorithmischen Versammlung in Europa ALGO. Detailliertere Informationen zum Wettbewerb selbst finden Sie auf Website, während die Ergebnisse der vergangenen Jahre liegen hier.

Lösungsansatz

Um das Problem der Knotenabdeckung zu lösen, habe ich versucht, parametrisierte Algorithmen anzuwenden. Diese bestehen in der Regel aus zwei Teilen: Vereinfachungsregeln (die idealerweise zu einer Kernelisierung führen) und Aufspaltungsregeln. Die Vereinfachungsregeln sind eine Vorverarbeitung des Eingangs in polynomieller Zeit. Das Ziel der Anwendung solcher Regeln besteht darin, das Problem auf eine äquivalente, kleinere Version zu reduzieren. Die Anwendung dieser Vereinfachungsregeln ist der arbeitsintensivste Teil des Algorithmus, und die Anwendung genau dieses Teils führt zu einer Gesamtlaufzeit anstatt zu einfacher polynomieller Zeit. In unserem Fall basieren die Aufspaltungsregeln darauf, dass für jeden Knoten entweder dieser oder sein Nachbar gewählt werden muss.

Das allgemeine Schema ist folgendes: Wir wenden die Vereinfachungsregeln an, wählen dann einen Knoten aus und machen zwei rekursive Aufrufe: im ersten nehmen wir ihn als Antwort, im anderen nehmen wir alle seine Nachbarn. Dies nennen wir das Aufspalten (Branching) über diesen Knoten.

In dieses Schema wird im nächsten Absatz genau eine Ergänzung aufgenommen.

Ideen für Aufspaltungsregeln (Branching)

Lassen Sie uns besprechen, wie man einen Knoten wählt, über den es zu einem Aufspalten kommt.
Die Hauptidee ist algorithmisch sehr gierig: Lassen Sie uns einen Knoten mit dem höchsten Grad nehmen und genau über ihn aufspalten. Warum scheint das besser zu sein? Weil wir im zweiten Zweig des rekursiven Aufrufs auf diese Weise sehr viele Knoten eliminieren. Man kann erwarten, dass ein kleiner Graph übrig bleibt, und auf diesem werden wir schnell arbeiten.

Dieser Ansatz mit den bereits besprochenen einfachen Kerntechniken zeigt sich als ziemlich effektiv und löst einige Tests mit mehreren Tausend Knoten. Aber zum Beispiel funktioniert er schlecht bei kubischen Graphen (d.h. Graphen, bei denen der Grad jedes Knotens drei beträgt).
Es gibt noch eine Idee, die auf einem ziemlich einfachen Gedanken basiert: Wenn der Graph nicht zusammenhängend ist, kann das Problem auf seinen Zusammenhangskomponenten unabhängig gelöst werden, indem die Antworten am Ende zusammengeführt werden. Das ist übrigens die kleine versprochene Modifikation im Schema, die die Lösung erheblich beschleunigen wird: Früher haben wir in einem solchen Fall mit dem Produkt der Zeiten zur Berechnung der Antworten der Komponenten gearbeitet, nun arbeiten wir mit der Summe. Und um das Branching zu beschleunigen, muss man einen zusammenhängenden Graph in einen nicht zusammenhängenden umwandeln.

Wie macht man das? Wenn im Graphen ein Schnittpunkt vorhanden ist, muss man genau an diesem schneiden. Ein Schnittpunkt ist ein Knoten, dessen Entfernung die Zusammenhängigkeit des Graphen beeinträchtigt. Alle Schnittpunkte im Graphen kann man mit einem klassischen Algorithmus in linearer Zeit finden. Dieser Ansatz beschleunigt das Schneiden erheblich.

Wenn einer der hervorgehobenen Knoten entfernt wird, zerfällt der Graph in Zusammenhängende Komponenten.

Das werden wir machen, aber ich möchte mehr. Zum Beispiel kleine Knoten-Schnitte im Graphen suchen und darauf das Schneiden durchführen. Der effektivste mir bekannte Weg, einen minimalen globalen Knoten-Schnitt zu finden, ist die Verwendung des Gomory-Hu-Baums, der in kubischer Zeit aufgebaut wird. Im PACE Challenge ist die typische Größe des Graphen mehrere tausend Knoten. In diesem Fall müssten wir in jedem Knoten des Rekursionsbaumes Milliarden von Operationen durchführen. Daher ist es einfach unmöglich, die Aufgabe in der vorgegebenen Zeit zu lösen.

Versuchen wir, die Lösung zu optimieren. Den minimalen Knoten-Schnitt zwischen einem Paar von Knoten kann man mit jedem Algorithmus finden, der den maximalen Fluss berechnet. Man kann ein Netzwerk darauf ansetzen den Dinic-Algorithmus, der in der Praxis sehr schnell funktioniert. Ich vermute, dass man theoretisch eine Abschätzung für die Laufzeit beweisen kann , was bereits sehr akzeptabel ist.

Ich habe mehrmals versucht, Schnitte zwischen Paaren zufälliger Knoten zu suchen und den ausgewogensten zu nehmen. Leider hat das in den offenen Tests der PACE Challenge schlechte Ergebnisse geliefert. Ich habe ihn mit einem Algorithmus verglichen, der auf den Knoten mit der höchsten Gradzahl basiert, und sie mit einer Begrenzung für die Tiefe gestartet. Nach dem Algorithmus, der versucht hat, den Schnitt auf diese Weise zu finden, lagen größere Graphen zurück. Das hängt damit zusammen, dass die Schnitte sehr unausgewogen waren: Wenn ich 5-10 Knoten entfernte, konnte ich nur 15-20 abtrennen.

Es ist anzumerken, dass in Artikeln über theoretisch schnellste Algorithmen deutlich fortgeschrittenere Techniken zur Auswahl von Knoten für das Schneiden verwendet werden. Diese Techniken haben jedoch eine sehr komplexe Umsetzung und oft schlechte Laufzeit- und Speicherschätzungen. Es ist mir nicht gelungen, davon praktikable zu extrahieren.

Anwendung der Vereinfachungsregeln

Wir haben bereits Ideen zur Kernalisierung. Ich erinnere daran:

1. Wenn es einen isolierten Knoten gibt, entferne ihn.
2. Wenn es einen Knoten der Stärke 1 gibt, entfernen Sie ihn und nehmen Sie seinen Nachbarn als Antwort.
3. Wenn es einen Knoten mit mindestens k + 1, nehmen Sie ihn als Antwort.

Mit den ersten beiden ist alles klar, aber mit dem dritten gibt es einen Trick. Wenn wir in der lustigen Aufgabe über die Bar eine obere Grenze für k, gegeben haben, müssen wir in der PACE Challenge einfach eine minimal große Deckung finden. Das ist eine typische Umwandlung von Suchproblemen in Entscheidungsprobleme; oft macht man zwischen den beiden Arten von Aufgaben keinen Unterschied. In der Praxis, wenn wir einen Solver für das Deckungsproblem schreiben, kann es einen Unterschied geben. Zum Beispiel, wie im dritten Punkt.

Aus der Sicht der Implementierung kann man auf zwei Arten vorgehen. Der erste Ansatz wird als Iterative Deepening bezeichnet. Er besteht darin, dass wir mit einer vernünftigen unteren Grenze für die Antwort beginnen und dann unseren Algorithmus ausführen, wobei wir diese Grenze als obere Grenze für die Antwort verwenden, ohne die Rekursion tiefer abzusteigen als diese Grenze. Wenn wir eine Antwort gefunden haben, ist sie garantiert optimal, andernfalls können wir diese Grenze um eins erhöhen und erneut starten.

Der andere Ansatz besteht darin, eine aktuelle optimale Antwort zu speichern und nach einer kleineren Antwort zu suchen und diesen Parameter bei der Auffindung zu ändern k um überflüssige Zweige in der Suche stärker abzuschneiden.

Nach einigen nächtlichen Experimenten habe ich mich für eine Kombination dieser beiden Methoden entschieden: Zunächst starte ich meinen Algorithmus mit einer Begrenzung der Suchtiefe (indem ich sie so wähle, dass sie im Vergleich zur Hauptlösung vernachlässigbare Zeit in Anspruch nimmt) und verwende die beste gefundene Lösung als obere Begrenzung für die Antwort — also genau für die k.

Knoten der Stärke 2

Mit Knoten der Stärken 0 und 1 sind wir durch. Es stellt sich heraus, dass das auch mit Knoten der Stärke 2 möglich ist, aber dafür sind komplexere Operationen am Graphen erforderlich.

Um das zu erklären, müssen wir die Knoten irgendwie kennzeichnen. Nennen wir einen Knoten der Stärke 2 einen Knoten v, und seine Nachbarn — Knoten x und y. Dann haben wir zwei Fälle.

1. Wenn x und y — Nachbarn. Dann kann man als Antwort nehmen x und y, und v entfernen. Und in der Tat, aus diesem Dreieck müssen mindestens zwei Knoten in die Antwort aufgenommen werden, und wir verlieren definitiv nicht, wenn wir nehmen x und y: Sie haben wahrscheinlich noch Nachbarn, während bei v diese nicht vorhanden sind.
2. Wenn x und y — keine Nachbarn. Dann wird behauptet, dass alle drei Eckpunkte zu einem zusammengefügt werden können. Die Idee ist, dass in diesem Fall eine optimale Antwort vorliegt, in der wir entweder v, oder beide Eckpunkte x und ynehmen müssen. Im ersten Fall müssen wir alle Nachbarn in die Antwort aufnehmen x und y, im zweiten Fall ist das nicht unbedingt erforderlich. Dies entspricht genau den Fällen, in denen wir den zusammengefügten Eckpunkt nicht in die Antwort aufnehmen und wenn wir es tun. Es bleibt nur zu bemerken, dass in beiden Fällen die Antwort durch diese Operation um eins verringert wird.

Es ist erwähnenswert, dass es ziemlich schwierig ist, einen solchen Ansatz in ehrlicher linearer Zeit sorgfältig zu implementieren. Das Zusammenfügen von Eckpunkten ist eine komplexe Operation, es müssen Nachbarlisten kopiert werden. Wenn dies nicht sorgfältig geschieht, kann es zu asymptotisch suboptimalen Laufzeiten kommen (zum Beispiel, wenn nach jeder Zusammenfügung viele Kanten kopiert werden). Ich konzentrierte mich auf die Suche nach vollständigen Wegen aus Eckpunkten der Ordnung 2 und die Analyse vieler spezieller Fälle, wie z. B. Zyklen aus solchen Eckpunkten oder aus allen solchen Eckpunkten außer einem.

Darüber hinaus muss dieser Vorgang umkehrbar sein, damit wir während der Rückkehr aus der Rekursion den Graphen in seinen ursprünglichen Zustand wiederherstellen können. Um dies zu gewährleisten, habe ich die Kantenlisten der zusammengefügten Eckpunkte nicht gelöscht; danach wusste ich einfach, wohin die Kanten gerichtet werden müssen. Eine solche Implementierung von Grafen erfordert ebenfalls Sorgfalt, bietet jedoch ehrliche lineare Zeit. Und für Grafen mit mehreren Zehntausend Kanten passt es gut in den Cache des Prozessors, was Geschwindigkeitsvorteile bietet.

Lineares Kern

Schließlich der interessanteste Teil des Kerns.

Zunächst erinnern wir uns daran, dass in bipartiten Grafen das minimale Vertex-Deckung in gesucht werden kann. Dazu muss der Algorithmus Hopcroft-Karp verwendet werden, um dort das maximale Paarung zu finden, und dann das Theorem Königs-Egervari.

anzuwenden. Die Idee des linearen Kerns ist folgende: Zunächst teilen wir den Graphen auf, d.h. anstelle jedes Eckpunkts v führen wir zwei Eckpunkte ein, und und anstelle jeder Kante u — v führen wir zwei Kanten ein. und Der erhaltene Graph wird bipartit sein. Wir werden darin das minimale Knotencover finden. Einige Knoten des ursprünglichen Graphen werden dort zweimal erscheinen, einige nur einmal und einige gar nicht. Der Satz von Nemhauser-Trotter besagt, dass wir in diesem Fall Knoten, die kein einziges Mal vorkommen, entfernen können und die diejenigen als Antwort nehmen, die zweimal vorkommen. Darüber hinaus sagt er, dass von den verbleibenden Knoten (denjenigen, die einmal vorkommen) mindestens die Hälfte als Antwort genommen werden sollte.

Gerade haben wir gelernt, im Graphen nicht mehr als 2k Knoten zu belassen. Es stimmt, wenn in der Überschussantwort mindestens die Hälfte aller Knoten vorhanden ist, dann sind es insgesamt nicht mehr als 2k.

Hier ist mir ein kleiner Schritt vorwärts gelungen. Es ist klar, dass der auf diese Weise konstruierte Kern davon abhängt, welches minimale Knotencover im bipartiten Graphen wir gewählt haben. Ich möchte eines wählen, bei dem die Anzahl der verbleibenden Knoten minimal ist. Früher konnte man das nur in einer Zeit von . Ich habe jedoch eine Implementierung dieses Algorithmus in einer Zeit von erfunden, sodass dieser Kern in Graphen mit Hunderttausenden von Knoten in jeder Phase des Branching gesucht werden kann.

Ergebnis

Die Praxis zeigt, dass meine Lösung in Tests mit mehreren Hundert Knoten und einigen Tausend Kanten gut funktioniert. Bei solchen Tests kann man ganz gut erwarten, dass die Lösung innerhalb einer halben Stunde gefunden wird. Die Wahrscheinlichkeit, dass die Antwort in akzeptabler Zeit gefunden wird, steigt grundsätzlich, wenn der Graph genügend viele Knoten hohen Grades hat, zum Beispiel Grad 10 und höher.

Um am Wettbewerb teilzunehmen, mussten die Lösungen bis zu optil.ioeingereicht werden. Anhand der dort vorgestellten Tabellenimmt meine Lösung in den offenen Tests den dritten Platz von zwanzig mit großem Abstand zum zweiten ein. Um ganz ehrlich zu sein, ist es nicht ganz klar, wie die Lösungen im Wettbewerb selbst bewertet werden: Zum Beispiel besteht meine Lösung aus weniger Tests als die Lösung auf dem vierten Platz, aber sie funktioniert bei denen, die sie besteht, schneller.

Die Ergebnisse der geschlossenen Tests werden am ersten Juli bekannt gegeben.

Quelle: habr.com