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

Die Komplexität von Graphenisomorphie und -kanonisierung ist eine der wichtigsten offenen Fragen der Theoretischen Informatik. BabaisIsomorphie-Algorithmus, der einen Durchbruch auf diesem Gebiet darstellt, wirft die spannende Frage auf, ob eine superpolynomielle Laufzeit beim Isomorphietest und bei der Kanonisierung inhärent ist oder ob sie nur durch die Begrenztheit der benutzten Ansätze verursacht wird. Wir konzentrieren uns auf kanonische Partitionierungstechniken, die einen Eckstein von Babais Ansatz bilden, und deren Potential noch nicht in vollem Maße ausgeschöpft zu sein scheint. Ein neuer Schwerpunkt der zweiten Projektphase liegt auf Querverbindungen mit anderen theoretischen Bereichen (kohärente Konfigurationen, Graph-Limit-Theorie) und auf Fragestellungen, die durch praktische Anwendungen motiviert sind (Analyse von Relaxationen NP-harter Optimierungsprobleme, Ähnlichkeitsmaße für große Graphen in der Künstlichen Intelligenz).

• DFG-Verfahren: Sachbeihilfen