Isomorphism Testing for Graphs Excluding Small Minors
Martin Grohe, Daniel Wiebking, Daniel Neuen · 2020
We prove that there is a graph isomorphism test running in time npolylog(h)on n-vertex graphs excluding some h-vertex graph as a minor. Previously known bounds were npoly(h)(Ponomarenko, 1988) and npolylog(n)(Babai, STOC 2016). For the algorithm we combine recent advances in the group-theoretic graph isomorphism machinery with new graph-theoretic arguments.