Isomorphism Testing Parameterized by Genus and Beyond

Abstract

We give an isomorphism test for graphs of Euler genus $g$ running in time $2^{O(g^4\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.

31 pages, 5 figure, full version of a paper accepted at ESA 2021; second version improves the presentation of the results

Cited by in corpus (1)

• The Iteration Number of the Weisfeiler-Leman Algorithm