Graph isomorphism in quasipolynomial time parameterized by treewidth

11/25/2019

∙

by   Daniel Wiebking, et al.

∙

0

∙

share

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^polylog(k) where n is the number of vertices and k is the maximum treewidth of the given graphs and polylog(k) is some polynomial in log(k). Our result generalizes Babai's quasipolynomial-time graph isomorphism test.