Graph Isomorphism in Quasipolynomial Time Parameterized by Treewidth

DROPS (Schloss Dagstuhl – Leibniz Center for Informatics)

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

Authors 1

1. Daniel Wiebking corresponding Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University, Germany

   RWTH Aachen University, Aachen, Germany