Isomorphism Testing for Graphs Excluding Small Topological Subgraphs

Daniel Neuen

We give an isomorphism test that runs in time $n^{\operatorname{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^{\operatorname{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^{\operatorname{polylog}(d)}$ (FOCS 2018) and for graphs of Hadwiger number $h$ running in time $n^{\operatorname{polylog}(h)}$ (FOCS 2020).

Knowledge Graph



Sign up or login to leave a comment