Current Challenges in Isomorphism Testing and Graph Canonization

• Applicant: Professor Dr. Johannes Köbler
• Subject Area: Theoretical Computer Science
• Term: from 2017 to 2024
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 383863674

The computational complexity of the graph isomorphism and canonization problems is one of the most important open questions in theory of computing. Babai's isomorphism algorithm, which is the major achievement in the field, poses a challenging question whether a superpolynomial running time is inherent to isomorphism testing and canonization or whether it is just caused by the limitations of the current methods. We focus on the canonical partitioning techniques, that are one of the cornerstones of Babai's approach and whose potential seems to be not recognized yet to full extent. A new focus of the second phase of the project is on interconnections with other theoretical areas (coherent configurations, graph limit theory) and on problems motivated by applications in practically oriented fields (analysis of relaxations of NP-hard optimization problems, estimation of similarity between large graphs in artificial intelligence).

• DFG Programme: Research Grants