Send email Copy Email Address
2020-11-16

Isomorphism Testing for Graphs Excluding Small Minors

Summary

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

Conference / Medium

2020 IEEE 61st Annual Symposium on Foundations of Computer Science

Date published

2020-11-16

Date last modified

2021-05-07 15:44:04