Isomorphism Testing for Graphs Excluding Small Minors

Annual Symposium on Foundations of Computer Science, vol. 168, pp. 625–636

Abstract

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.

Authors 3

1. Martin Grohe Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University, Aachen, Germany

2. Daniel Wiebking Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University, Aachen, Germany

3. Daniel Neuen

   Helmholtz Center for Information Security

   Affiliation as printed

   CISPA Helmholtz Center for Information Security, Saarbrücken, Germany