Isomorphism Testing for Graphs Excluding Small Minors

Abstract

We prove that there is a graph isomorphism test running in time $n^{\mathrm{polylog}(h)}$ on $n$-vertex graphs excluding some $h$-vertex graph as a minor. Previously known bounds were $n^{\mathrm{poly}(h)}$ (Ponomarenko, 1988) and $n^{\mathrm{polylog}(n)}$ (Babai, STOC 2016). For the algorithm we combine recent advances in the group-theoretic graph isomorphism machinery with new graph-theoretic arguments.

33 pages, 7 figures, full version of a paper accepted at FOCS 2020; second version improves the presentation of the results