Isomorphism Testing Parameterized by Genus and Beyond

DROPS (Schloss Dagstuhl – Leibniz Center for Informatics)

Abstract

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.

Authors 1

1. Daniel Neuen corresponding Aachen

   RWTH Aachen University · Helmholtz Center for Information Security

   Affiliation as printed

   CISPA Helmholtz Center for Information Security, Saarland Informatics Campus, Saarbrücken, Germany

   RWTH Aachen University, Aachen, Germany