2026-07-23T07:03:04Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12510 2024-03-06T10:50:19Z ddc:004 open_access

Graph Isomorphism in Quasipolynomial Time Parameterized by Treewidth Wiebking, Daniel Graph isomorphism canonization treewidth hypergraphs 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Daniel Wiebking 2020 Is Part Of LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2020.103 urn:nbn:de:0030-drops-125106 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.103 eng https://creativecommons.org/licenses/by/3.0/legalcode