Aktuelle Herausforderungen beim Isomorphietest und bei der Kanonisierung von Graphen

• Antragsteller: Professor Dr. Johannes Köbler
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2017 bis 2024
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 383863674

• Erstellungsjahr: 2024

Zusammenfassung der Projektergebnisse

Die Berechnungskomplexität der Isomorphie- und Kanonisierungsprobleme für Graphen gehört zu den bedeutendsten offenen Fragen der Theoretischen Informatik. Babais Isomorphiealgorithmus (2016) ist ein herausragender Erfolg in diesem Bereich und wirft die Frage auf, ob eine superpolynomiale Laufzeit inhärent für das Graphisomorphieproblem ist oder ob sie lediglich auf die Begrenzungen der derzeit verfügbaren Methoden zurückzuführen ist. Dieses Projekt konzentriert sich hauptsächlich auf kombinatorische Verfeinerungstechniken, die ein wesentlicher Bestandteil von Babais Ansatz sind. Unser übergeordnetes Ziel ist es hierbei, diejenigen “Teile” des Problems möglichst präzise zu identifizieren, die sich mit diesen Techniken effizient lösen lassen. Es ist bekannt, dass eine relativ einfache kombinatorische Verfeinerungsmethode ein effizientes Werkzeug zur Kanonisierung fast aller Graphen ist. Insbesondere produziert diese Methode für einen zufällig ausgewählten Graphen mit hoher Wahrscheinlichkeit eine kanonische Form. Der Erfolg der kombinatorischen Verfeinerung bei zufälligen Graphen beruht darauf, dass ein zufällig gewählter Graph mit hoher Wahrscheinlichkeit asymmetrisch ist. Wir zeigen, dass kombinatorische Verfeinerung auch bei Graphen mit Symmetrien (d.h. solchen, die nicht-triviale Automorphismen zulassen) effektiv sein kann. Unsere Analyse umfasst zwei unterschiedliche Fälle: spärliche Zufallsgraphen im evolutionären Erdős-Rényi-Modell und vertex-transitive Graphen. Ein weiteres Ziel unserer Forschung ist es, eine effizient überprüfbare Charakterisierung derjenigen Graphen zu erhalten, die “einfache Instanzen” für einen bestimmten Isomorphie- Testansatz sind. Wir lösen dieses Problem für den 2-dimensionalen Weisfeiler-Leman (WL) Algorithmus im Kontext von Graphen mit geringer Farbenvielfalt. Dieser Fall ist besonders interessant, da er die berühmten Cai-Fürer-Immerman-Graphen umfasst, die eine erhebliche Herausforderung für den WL-Algorithmus in jeder Dimension darstellen. Ein wesentlicher Teil unserer Arbeit betrifft WL-invariante Graphparameter, das heißt, Parameter, die bei je zwei vom WL-Algorithmus nicht unterscheidbaren Graphen übereinstimmen. Die in diese Richtung erzielten Ergebnisse sind für mehrere andere Bereiche relevant, darunter das Design von Graph Neuronalen Netzen, die chemische Graphentheorie, die Analyse von LP-Relaxationen von NP-schweren Optimierungsproblemen und die Kombinatorik.

Link zum Abschlussbericht

https://doi.org/10.18452/33141

Projektbezogene Publikationen (Auswahl)

• Tight Bounds on the Asymptotic Descriptive Complexity of Subgraph Isomorphism. ACM Transactions on Computational Logic, 20(2), 1-18.
  Verbitsky, Oleg & Zhukovskii, Maksim
  
• On Weisfeiler-Leman invariance: Subgraph counts and related graph properties. Journal of Computer and System Sciences, 113, 42-59.
  Arvind, V.; Fuhlbrück, Frank; Köbler, Johannes & Verbitsky, Oleg
  
• Identifiability of Graphs with Small Color Classes by the Weisfeiler--Leman Algorithm. SIAM Journal on Discrete Mathematics, 35(3), 1792-1853.
  Fuhlbrück, Frank; Köbler, Johannes & Verbitsky, Oleg
  
• Local WL invariance and hidden shades of regularity. Discrete Applied Mathematics, 305, 191-198.
  Fuhlbrück, Frank; Köbler, Johannes & Verbitsky, Oleg
  
• The Weisfeiler-Leman algorithm and recognition of graph properties. Theoretical Computer Science, 895, 96-114.
  Fuhlbrück, Frank; Köbler, Johannes; Ponomarenko, Ilia & Verbitsky, Oleg
  
• On Anti-stochastic Properties of Unlabeled Graphs. Lecture Notes in Computer Science, 300-312. Springer International Publishing.
  Kiselev, Sergei; Kupavskii, Andrey; Verbitsky, Oleg & Zhukovskii, Maksim
  
• On the Weisfeiler-Leman dimension of fractional packing. Information and Computation, 288, 104803.
  Arvind, V.; Fuhlbrück, Frank; Köbler, Johannes & Verbitsky, Oleg
  
• Canonization of a random graph by two matrix-vector multiplications. In Proc. of the 31st Ann. European Symposium on Algorithms (ESA’23), volume 274 of LIPIcs, pages 100:1–100:13.
  O. Verbitsky & M. Zhukovskii
  
• Canonical labeling of sparse random graphs
  O. Verbitsky & M. Zhukovskii
  
• Canonization of a Random Circulant Graph by Counting Walks. Lecture Notes in Computer Science, 319-334. Springer Nature Singapore.
  Verbitsky, Oleg & Zhukovskii, Maksim
  
• Combinatorial refinement on circulant graphs. computational complexity, 33(2).
  Kluge, Laurence
  
• Gathering information about a graph by counting walks from a single vertex
  F. Fuhlbrück, J. Köbler, O. Verbitsky & M. Zhukovskii
  
• On a hierarchy of spectral invariants for graphs. In Proc. of the 41st Int. Symposium on Theoretical Aspects of Computer Science, (STACS’24), volume 289 of LIPIcs, pages 6:1–6:18
  V. Arvind, F. Fuhlbrück, J. Köbler & O. Verbitsky
  
• New Bounds for the Optimal Density of Covering Single-Insertion Codes via the Turán Density. IEEE Transactions on Information Theory, 71(6), 4260-4266.
  Pikhurko, Oleg; Verbitsky, Oleg & Zhukovskii, Maksim
  
• On the expressibility of the reconstructional color refinement. Theoretical Computer Science, 1047, 115321.
  Arvind, V.; Köbler, Johannes & Verbitsky, Oleg