Graph isomorphism in quasipolynomial time [extended abstract]

By László Babai. Symposium on the Theory of Computing, 2015

632 citations recorded by the source corpus.

We show that the Graph Isomorphism (GI) problem and the more general problems of String Isomorphism (SI) andCoset Intersection (CI) can be solved in quasipolynomial(exp((logn)O(1))) time. The best previous bound for GI was exp(O( √n log n)), where n is the number of vertices (Luks, 1983); for the other two problems, the bound was similar, exp(O~(√ n)), where n is the size of the permutation domain (Babai, 1983). Following the approach of Luks’s seminal 1980/82 paper, the problem we actually address is SI. This problem takes two strings of length n and a permutation group G of degree n (the “ambient group”) as input (G is given by a list of generators) and asks whether or not one of the strings can be transformed into the other by some element of G. Luks’s divide-and-conquer algorithm for SI proceeds by recursion on the ambient group. We build on Luks’s framework and attack the obstructions to efficient Luks recurrence via an interplay between local and global symmetry. We construct group theoretic “local certificates” to certify the presence or absence of local symmetry, aggregate the negative certificates to canonical k-ary relations where k = O(log n), and employ combinatorial canonical partitioning techniques to split the k-ary relational structure for efficient divide-and- conquer. We show that in a well–defined sense, Johnson graphs are the only obstructions to effective canonical partitioning. The central element of the algorithm is the “local certificates” routine which is based on a new group theoretic result, the “Unaffected stabilizers lemma,” that allows us to construct global automorphisms out of local information.

Subfields: Computational Theory and Mathematics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/12fc55090dceb389d526aefd956cad3a211105af

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Geometry and Topology

Citations in the corpus

Towards a practical k-dimensional Weisfeiler-Leman algorithm (2019, methodology): “Most practical successful solvers for the graph isomorphism problem, such as nauty [26, 23], as well as the theoretically fastest state-of-the-art graph isomorphism algorithm [4] are rely on vertex refinement.”
Hodge Laplacians on graphs (2015, background): “6An astounding recent result of Babai [5] is that there is a quasipolynomial-time algorithm.”
Anonymous Walk Embeddings (2018, background): “However, such algorithm would be capable of deciding whether two graphs are isomorphic (G¨artner et al., 2003), for which currently only quasipolynomial-time algorithm exists (Babai, 2016).”
Adiabatic Quantum Computing (2016, background): “However, a recent breakthrough gave a quasipolynomial (exp[(log n)O(1)]) time classical algorithm for graph isomorphism (Babai, 2015).”