A decomposition-compatible canonization framework for the graph isomorphism problem

Wiebking, Daniel; Grohe, Martin (Thesis advisor); Schweitzer, Pascal (Thesis advisor); Torán, Jacobo (Thesis advisor)

Aachen : RWTH Aachen University (2021)
Doktorarbeit

Dissertation, RWTH Aachen University, 2021

Kurzfassung

Das Graphisomorphie-Problem ist eines der wenigen berühmten Probleme in NP, von dem weder bekannt ist, dass es in polynomieller Zeit lösbar ist, noch dass es NP-vollständig ist. Das Problem fragt, ob zwei gegebene Eingabegraphen strukturell äquivalent sind, was bedeutet, dass beide Graphen bis auf eine Umbenennung der Knoten übereinstimmen. Mit dem gefeierten Durchbruch von Babai (STOC 2016) wurde gezeigt, dass das Problem in Quasipolynomialzeit gelöst werden kann. Eine Möglichkeit, das Graphisomorphie-Problem zu lösen, ist durch Anwendung eines Kanonisierungsansatzes. Die Kanonisierung eines Graphen ist die Aufgabe der Transformation in eine kanonische Form, das heißt eine Graphendarstellung, die für strukturell äquivalente Graphen übereinstimmt. Soweit wir wissen, könnte die Graphenkanonisierung schwieriger sein als das Graphisomorphie-Problem. Insbesondere gibt es Isomorphietests für verschiedene Graphenklassen und Objekte, für die bis heute kein Kanonisierungsalgorithmus mit gleicher asymptotischer Laufzeit bekannt ist. In dieser Arbeit entwerfen wir ein vereinheitlichendes Kanonisierungsgerüst für Graphen und darüber hinaus für kombinatorische Objekte im Allgemeinen. Wir verwenden das Gerüst, um neue, schnellste Kanonisierungsalgorithmen mit einer asymptotischen Laufzeit zu entwerfen, die den besten bekannten Isomorphietests entspricht. Unser Gerüst unterstützt die Verwendung von Dekompositionstechniken. Durch die Kombination unseres Gerüsts mit neuen graphentheoretischen Dekompositionen können wir der Laufzeit bestehender Isomorphietests für Graphen mit beschränkter Baumweite und Graphen mit festen ausgeschlossenen Minoren nicht nur gleichkommen, sondern diese sogar verbessern. Unsere verbesserten Algorithmen für eingeschränkte Graphenklassen gehen Hand in Hand mit neuen Erkenntnissen über die Automorphismengruppen. Wir beweisen mehrere Restriktionen für diese Gruppen, indem wir sie von einem rein mathematischen Standpunkt aus analysieren. Darüber hinaus hat unser dekompositionsfreundliches Gerüst auch Anwendungen in der rechnergestützten Gruppentheorie. Insbesondere entwerfen wir einen neuen schnellsten Algorithmus zur Berechnung von Normalisatoren von Permutationsgruppen. Schließlich untersuchen wir die Verbindungen zwischen Isomorphietestung und Kanonisierung aus einer logischen Perspektive. Zu diesem Zweck stellen wir ein neues Berechnungsmodell bereit, das eine Konstruktion unterstützt, die Isomorphietests in Kanonisierungsalgorithmen umwandelt.