Logik, Struktur und das Graphenisomorphieproblem

• Applicant: Professor Dr. Martin Grohe
• Subject Area: Theoretical Computer Science
• Term: from 2012 to 2020
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 217526258

• Final Report Year: 2021

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
  
• “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
  
• “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
  
• “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
  
• “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
  
• “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
  
• “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
  
• “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
  
• “The Graph Isomorphism Problem”. In: Communications of the ACM 63.11 (2020), S. 128–134
  M. Grohe und P. Schweitzer
  
• “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