The power of algorithmic approaches to the graph isomorphism problem

• Die Stärke algorithmischer Ansätze für das Graphisomorphieproblem

Neuen, Daniel; Grohe, Martin (Thesis advisor); Schweitzer, Pascal (Thesis advisor); Babai, László (Thesis advisor)

Aachen (2019, 2020)
Doktorarbeit

Dissertation, RWTH Aachen University, 2019

Kurzfassung

Das Graphisomorphieproblem fragt, gegeben zwei Graphen, ob diese strukturell identisch sind, d.h. ob man durch Umbenennung der Knoten des ersten Graphen diesen in den zweiten Graphen transformieren kann. Mit dem jüngsten Durchbruch von Babai (STOC 2016) kann dieses Problem in quasipolynomieller Zeit gelöst werden. Jedoch bleibt es, trotz intensiver Forschung, eines von nur wenigen natürlichen Problemen in NP, für das weder ein Polynomialzeitalgorithmus noch die NP-Schwere bekannt ist. In den letzten fünf Jahrzehnten wurden vielfältige algorithmische Techniken für das Graphisomorphieproblem erforscht, was überraschende Verbindungen zwischen verschiedenen Ansätzen hervorgebracht hat. Außerdem führte dies zu zahlreichen Algorithmen, die das Isomorphieproblem auf eingeschränkten Klassen von Eingabegraphen lösen. Diese Dissertation verfolgt das Ziel unser Verständnis über Stärken und Grenzen verschiedener wichtiger Ansätze zum Graphisomorphieproblem zu erweitern. Dies resultiert insbesondere in mehreren verbesserten Algorithmen die das Isomorphieproblem für wichtige Klassen von Graphen lösen. Eine der grundlegendsten Methoden für das Testen von Isomorphie ist der Weisfeiler-Leman Algorithmus, der iterativ eine isomorphieinvariante Färbung der Knotentupel berechnet. Obwohl dieser Algorithmus das Isomorphieproblem nicht alleine lösen kann, wird er regelmäßig als Unterprogramm verwendet und dient als vollständiger Isomorphietest für mehrere eingeschränkte Klassen von Graphen. In diesen Zusammenhang zeigen wir, dass die Weisfeiler-Leman Dimension von Graphen beschränkter Rangweite beschränkt ist. Während ein Polynomialzeitalgorithmus für das Isomorphieproblem von Graphen mit Rangweite höchstens k bereits vorher bekannt war (Grohe und Schweitzer, FOCS 2015), so sind bisherige Algorithmen kompliziert und der Exponent der Laufzeit hängt nicht-elementar von k ab. Im Gegensatz dazu ergibt unsere Analyse des Weisfeiler-Leman Algorithmus einen einfachen Isomorphietest mit Laufzeit n^{O(k)}. Ein mit dem Weisfeiler-Leman Algorithmus eng verwandter Ansatz, der besonders gut in der Praxis funktioniert, ist das Paradigma des Individualisierens und Verfeinerns. Um unser Verständnis der Grenzen kombinatorischer Ansätze zu erweitern, geben wir die ersten exponentiellen unteren Schranken für die Laufzeit einer großen und natürlichen Klasse von Algorithmen innerhalb dieses Paradigmas. Insbesondere erhalten wir exponentielle untere Schranken für die Laufzeit sämtlicher moderner praktischer Isomorphieprogramme und beantworten damit eine offene Frage von Babai (STOC 2016). Ein zweiter fundamentaler Ansatz für das Graphisomorphieproblem ist die Verwendung gruppentheoretischer Methoden. In dieser Hinsicht ist Luks Algorithmus für das Testen von Isomorphie von Graphen beschränkten Grades einer der Grundpfeiler der algorithmischen Theorie des Graphisomorphieproblems. Indem wir die gruppentheoretischen Methoden, die Babai für seinen Quasipolynomialzeitalgorithmus entwickelt hat, anpassen, erhalten wir einen Isomorphietest für Graphen mit Maximalgrad höchstens d mit einer Laufzeit von n^{polylog(d)}. Dies stellt eine deutliche Verbesserung im Vergleich zum bisher schnellsten Algorithmus für dieses Problem dar, welcher n^{O(d / log d)} Schritte benötigt (Babai, Kantor und Luks, FOCS 1983). Da Luks Algorithmus als Unterprogramm für eine Reihe weiterer Algorithmen dient, stellt sich die Frage welche Konsequenzen sich aus obiger Verbesserung ergeben. Neben einfachen Anwendungen für das Isomorphieproblem von relationalen Strukturen mit kleinem Grad zeigen wir, dass man Isomorphie von Graphen mit Baumweite höchstens k in Zeit 2^{k polylog(k)} poly(n) testen kann und verbessern damit den FPT-Algorithmus von Lokshtanov et al.\ (FOCS 2014) mit Laufzeit 2^{O(k^{5} log k)} poly(n).