Graph isomorphism in quasipolynomial time parameterized by treewidth

Abstract

We extend Babai's quasipolynomial-time graph isomorphism test (STOC 2016) and develop a quasipolynomial-time algorithm for the multiple-coset isomorphism problem. The algorithm for the multiple-coset isomorphism problem allows to exploit graph decompositions of the given input graphs within Babai's group-theoretic framework. We use it to develop a graph isomorphism test that runs in time $n^{\mathrm{polylog}(k)}$ where $n$ is the number of vertices and $k$ is the minimum treewidth of the given graphs and $\mathrm{polylog}(k)$ is some polynomial in $\log (k)$. Our result generalizes Babai's quasipolynomial-time graph isomorphism test.

52 pages, 1 figure