Logik, Struktur und das Graphenisomorphieproblem
Final Report Abstract
Thema des Projekts war das Graphenisomorphiproblem (GI), also das algorithmische Problem, zu entscheiden, ob zwei Graphen isomorph sind. Es ist ein wichtiges, seit 50 Jahren offenes Problem, die Komplexität von GI zu bestimmen. Technisch bewegt sich das Projekt im Zusammenspiel von Gruppentheorie, kombinatorischen Algorithmen, Logik, und struktureller Graphentheorie. Die Hauptresultate sind: 1. Eine Reihe von quasipolynomiellen parametrisierten Algorithmen für GI mit eine Laufzeit n^polylog k, wobei n die Ordnung der Eingabegraphen ist und k einer der Pärämeter Maximalgrad, Genus, Baumweite, Hadwigerzahl. Unsere strukturellen Ansätze haben hier auch zu neuen Einsichten in die Automorphismengruppen von Graphen mit verbotenen Minoren geführt. 2. Ein umfassende Analyse des Weisfeiler-Leman Algorithmus und seiner wichtigen Parameter Iterationszahl und Dimension. Hier ist das wichtigste Einzelergebnis, dass die WL Dimension von planaren Graphen höchsten 3 ist. Ebenfalls konnten wir zahlreiche Verbindungen zwischen WL Algorithmus und algebraischen Ansätzen zum Isomorphieproblem herstellen. Darüber hinaus haben wir erst Resultate zum Graphähnlichkeitsproblem erzielt, das für Anwendungen insbesondere im maschinellen Lernen von großer Bedeutung ist. Interessant sind hier insbesondere eine Reihe von Resultaten zum Zählen von Homomorphismen und Homomorphismenvektoren. Wir konnten auch direkte Verbindungen zwischen WL-Algorithmus und Techniken des maschinellen Lernens herstellen.
Publications
- “Linear Diophantine Equations, Group CSPs, and Graph Isomorphism”. In: Proceedings of the of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms. 2017, S. 327–339
C. Berkholz und M. Grohe
(See online at https://doi.org/10.1137/1.9781611974782.21) - “A Faster Isomorphism Test for Graphs of Small Degree”. In: SIAM Journal on Computing (2020). Special Section FOCS 2018
M. Grohe, D. Neuen und P. Schweitzer
(See online at https://doi.org/10.1137/19M1245293) - “An exponential lower bound for individualization-refinement algorithms for graph isomorphism”. In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. 2018, S. 138–150
D. Neuen und P. Schweitzer
(See online at https://doi.org/10.1145/3188745.3188900) - “A unifying method for the design of algorithms canonizing combinatorial objects”. In: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. 2019, S. 1247–1258
P. Schweitzer und D. Wiebking
(See online at https://doi.org/10.1145/3313276.3316338) - “Canonisation and Definability for Graphs of Bounded Rank Width”. In: Proceedings of the 34th ACM-IEEE Symposium on Logic in Computer Science. 2019, S. 1–13
M. Grohe und D. Neuen
(See online at https://doi.org/10.1109/LICS.2019.8785682) - “The Weisfeiler-Leman Dimension of Planar Graphs Is at Most 3”. In: J. ACM 66.6 (2019), 44:1–44:31
S. Kiefer, I. Ponomarenko und P. Schweitzer
(See online at https://doi.org/10.1145/3333003) - “An improved isomorphism test for bounded-tree-width graphs”. In: ACM Transactions on Algorithms 16.3 (2020), 34:1–34:31
M. Grohe, D. Neuen, P. Schweitzer und D. Wiebking
(See online at https://doi.org/10.1145/3382082) - “Isomorphism Testing for Graphs Excluding Small Minors”. In: Proceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science. 2020, S. 625–636
M. Grohe, D. Neuen und D. Wiebking
(See online at https://doi.org/10.1109/FOCS46700.2020.00064) - “The Graph Isomorphism Problem”. In: Communications of the ACM 63.11 (2020), S. 128–134
M. Grohe und P. Schweitzer
(See online at https://doi.org/10.1145/3372123) - “Deep Weisfeiler Leman”. In: Proceedings of the 32nd ACM-SIAM Symposium on Discrete Algorithms. 2021, S. 2600–2614
M. Grohe, P. Schweitzer und D. Wiebking
(See online at https://doi.org/10.1137/1.9781611976465.154)
