Creative Commons Attribution 4.0 license (CC BY 4.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2021.72
URN: urn:nbn:de:0030-drops-146533
URL: https://drops.dagstuhl.de/opus/volltexte/2021/14653/
Neuen, Daniel
Isomorphism Testing Parameterized by Genus and Beyond
| pdf-format: |
|
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.
BibTeX - Entry
@InProceedings{neuen:LIPIcs.ESA.2021.72,
author = {Neuen, Daniel},
title = {{Isomorphism Testing Parameterized by Genus and Beyond}},
booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)},
pages = {72:1--72:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-204-4},
ISSN = {1868-8969},
year = {2021},
volume = {204},
editor = {Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14653},
URN = {urn:nbn:de:0030-drops-146533},
doi = {10.4230/LIPIcs.ESA.2021.72},
annote = {Keywords: graph isomorphism, fixed-parameter tractability, Euler genus, Weisfeiler-Leman algorithm}
}
| Keywords: | graph isomorphism, fixed-parameter tractability, Euler genus, Weisfeiler-Leman algorithm | |
| Seminar: | 29th Annual European Symposium on Algorithms (ESA 2021) | |
| Issue date: | 2021 | |
| Date of publication: | 31.08.2021 |
