Recent advances on the graph isomorphism problem

MaRDI QIDQ5051745zbMATH OpenFDO

Authors Martin Grohe, Daniel Neuen

Publication date 18 November 2022

Full work available at URL https://arxiv.org/abs/2011.01366, https://www.cambridge.org/core/books/surveys-in-combinatorics-2021/recent-advances-on-the-graph-isomorphism-problem/2966D84DB2220F6A305472EE73B7973C

zbMATH Keywords

Babai's quasi-polynomial time isomorphism testcombinatorial Weisfeiler-Leman algorithm

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Abstract: We give an overview of recent advances on the graph isomorphism problem. Our main focus will be on Babai's quasi-polynomial time isomorphism test and subsequent developments that led to the design of isomorphism algorithms with a quasi-polynomial parameterized running time of the from $n^{extpolylog(k)}$, where $k$ is a graph parameter such as the maximum degree. A second focus will be the combinatorial Weisfeiler-Leman algorithm.

Recommendations

• Graph isomorphisms in quasi-polynomial time [after Babai and Luks, Weisfeiler-Leman,\ldots]
• Graph isomorphism in quasipolynomial time (extended abstract)
• On tractable parameterizations of graph isomorphism
• An improved isomorphism test for bounded-tree-width graphs
• The Weisfeiler-Lehman procedure

Cited in

(12)

• The graph isomorphism problem and approximate categories
• Some recognition problems related to graph isomorphism
• scientific article; zbMATH DE number 4073256 (Why is no real title available?)
• Graph isomorphisms in quasi-polynomial time [after Babai and Luks, Weisfeiler-Leman,\ldots]
• Graph isomorphism in quasipolynomial time (extended abstract)
• Order Reconfiguration under Width Constraints
• A Faster Isomorphism Test for Graphs of Small Degree
• Isomorphism for tournaments of small twin width
• Isomorphism testing for graphs excluding small topological subgraphs
• The Sherali-Adams and Weisfeiler-Leman hierarchies in (promise valued) constraint satisfaction problems
• A lower bound for the Weisfeiler-Leman dimension of circulant graphs
• Supercritical size-width tree-like resolution trade-offs for graph isomorphism

This page was built for publication: Recent advances on the graph isomorphism problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5051745)