Graph isomorphism in quasipolynomial time parameterized by treewidth

2019/11/25 by Daniel Wiebking, Wiebking, Daniel · 1 citation
Computer Science · Mathematics · #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics #G.2.2 #Group Theory (math.GR) #cs.CC #cs.DM #cs.DS #math.GR

paper · pdf · doi:10.48550/arxiv.1911.11257

52 pages, 1 figure

arxiv created 2020/04/20 · arxiv updated 2020/04/21

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.

Cited by

• Procountable groups are not classifiable by countable structures

Related

• An improved isomorphism test for bounded-tree-width graphs
• Recent Advances on the Graph Isomorphism Problem
• Graph Isomorphism in Quasipolynomial Time
• Graph isomorphism in quasipolynomial time [extended abstract]
• Isomorphismes de graphes en temps quasi-polynomial (d'après Babai et Luks, Weisfeiler-Leman...)