Isomorphism Testing for Graphs Excluding Small Minors

SIAM Journal on Computing, vol. 52, pp. 238–272

Abstract

Abstract. We prove that there is a graph isomorphism test running in time [Formula: see text] on [Formula: see text]-vertex graphs excluding some [Formula: see text]-vertex graph as a minor. Previously known bounds were [Formula: see text] [I. N. Ponomarenko, J. Soviet Math., 55 (1991), pp. 1621–1643] and [Formula: see text] [L. Babai, Proceedings of the 48 th Annual ACM Symposium on Theory of Computing, 2016, pp. 684–697]. 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 Neuen corresponding

   Simon Fraser University

   Affiliation as printed

   Simon Fraser University, Burnaby V5A 1S6, BC, Canada

3. Daniel Wiebking Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University, Aachen, Germany