Graph isomorphisms in quasi-polynomial time

By Harald Andrés Helfgott, Jitendra Bajpai, D. Dona. 2017

51 citations recorded by the source corpus.

Let us be given two graphs $\Gamma_1$, $\Gamma_2$ of $n$ vertices. Are they isomorphic? If they are, the set of isomorphisms from $\Gamma_1$ to $\Gamma_2$ can be identified with a coset $H\cdot\pi$ inside the symmetric group on $n$ elements. How do we find $\pi$ and a set of generators of $H$? The challenge of giving an always efficient algorithm answering these questions remained open for a long time. Babai has recently shown how to solve these problems -- and others linked to them -- in quasi-polynomial time, i.e. in time $\exp\left(O(\log n)^{O(1)}\right)$. His strategy is based in part on the algorithm by Luks (1980/82), who solved the case of graphs of bounded degree.

Subfields: Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/6c9b27ea7412d1ee57a34849e90f4e0e77b1f8c3

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

1. Jennifer Neville
2. Cong Hao
3. Pan Li
4. Susheel Suresh

Citations in the corpus

• Adversarial Graph Augmentation to Improve Graph Contrastive Learning (2021, background): “The best algorithm till now has complexity where n is the size of the graphs of interest [82].”