Graph isomorphism in quasipolynomial time parameterized by treewidth

arXiv1911.11257MaRDI QIDQ6329863FDOQ6329863

Authors: Daniel Wiebking 

Publication date: 25 November 2019

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

This page was built for publication: Graph isomorphism in quasipolynomial time parameterized by treewidth

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