Isomorphism Testing Parameterized by Genus and Beyond

Neuen, Daniel
(2021) Isomorphism Testing Parameterized by Genus and Beyond.
In: UNSPECIFIED.
Conference: ESA European Symposium on Algorithms
(Submitted)

[img] Text
gi-fpt-genus-esa.pdf

Download (704kB)

Abstract

We present 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.

Actions

Actions (login required)

View Item View Item