posted on 2023-11-29, 18:19authored byDaniel Neuen
We give an isomorphism test that runs in time n^{polylog(h)} on all n-vertex graphs excluding some h-vertex graph as a topological subgraph. Previous results state that isomorphism for such graphs can be tested in time n^{polylog(n)} (Babai, STOC 2016) and n^{f(h)} for some function $f$ (Grohe and Marx, SIAM J. Comp., 2015).
Our result also unifies and extends previous isomorphism tests for graphs of maximum degree d running in time n^{polylog(d)} (FOCS 2018) and for graphs of Hadwiger number h running in time n^{polylog(h)} (FOCS 2020).
History
Preferred Citation
Daniel Neuen. Isomorphism Testing for Graphs Excluding Small Topological Subgraphs. In: ACM-SIAM Symposium on Discrete Algorithms (SODA). 2022.
Primary Research Area
Algorithmic Foundations and Cryptography
Name of Conference
ACM-SIAM Symposium on Discrete Algorithms (SODA)
Legacy Posted Date
2021-12-14
Open Access Type
Gold
BibTeX
@inproceedings{cispa_all_3508,
title = "Isomorphism Testing for Graphs Excluding Small Topological Subgraphs",
author = "Neuen, Daniel",
booktitle="{ACM-SIAM Symposium on Discrete Algorithms (SODA)}",
year="2022",
}