Isomorphism Testing for Graphs Excluding Small Topological Subgraphs

Abstract

We give an isomorphism test that runs in time $n^{\mathrm{polylog}(h)}$ on all $n$-vertex graphs excluding some $h$-vertex vertex graph as a topological subgraph. Previous results state that isomorphism for such graphs can be tested in time $n^{\mathrm{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^{\mathrm{polylog}(d)}$ (SIAM J. Comp., 2023) and for graphs of Hadwiger number $h$ running in time $n^{\mathrm{polylog}(h)}$ (SIAM J. Comp., 2023).

42 pages, 3 figures, full version of a paper accepted at SODA 2022; second and third version improve the presentation of the results. arXiv admin note: text overlap with arXiv:2004.07671

References in corpus (3)

• The Power of the Weisfeiler-Leman Algorithm to Decompose Graphs
• Hypergraph Isomorphism for Groups with Restricted Composition Factors
• Isomorphism Testing for Graphs Excluding Small Minors

Cited by in corpus (1)

• The Iteration Number of the Weisfeiler-Leman Algorithm