2026-07-22T11:59:49Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14653 2024-03-06T10:54:33Z ddc:004 open_access

Isomorphism Testing Parameterized by Genus and Beyond Neuen, Daniel graph isomorphism fixed-parameter tractability Euler genus Weisfeiler-Leman algorithm We present an isomorphism test for graphs of Euler genus g running in time 2^{{O}(g⁴ log g)}n^{{O}(1)}. Our algorithm provides the first explicit upper bound on the dependence on g for an fpt isomorphism test parameterized by the Euler genus of the input graphs. The only previous fpt algorithm runs in time f(g)n for some function f (Kawarabayashi 2015). Actually, our algorithm even works when the input graphs only exclude K_{3,h} as a minor. For such graphs, no fpt isomorphism test was known before. The algorithm builds on an elegant combination of simple group-theoretic, combinatorial, and graph-theoretic approaches. In particular, we introduce (t,k)-WL-bounded graphs which provide a powerful tool to combine group-theoretic techniques with the standard Weisfeiler-Leman algorithm. This concept may be of independent interest. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Daniel Neuen 2021 Is Part Of LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2021.72 urn:nbn:de:0030-drops-146533 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.72 eng https://creativecommons.org/licenses/by/4.0/legalcode