(2021) Isomorphism Testing Parameterized by Genus and Beyond.
|
Text
LIPIcs-ESA-2021-72.pdf - Published Version Available under License Creative Commons Attribution. Download (798kB) | Preview |
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.
| Item Type: | Conference or Workshop Item (A Paper) (Paper) |
|---|---|
| Divisions: | Dániel Marx (DM) |
| Conference: | ESA European Symposium on Algorithms |
| Depositing User: | Daniel Neuen |
| Date Deposited: | 04 Aug 2021 10:47 |
| Last Modified: | 12 Oct 2022 19:02 |
| Primary Research Area: | NRA1: Trustworthy Information Processing |
| URI: | https://publications.cispa.saarland/id/eprint/3458 |
Actions
Actions (login required)
 |
View Item |