Isomorphism Testing for Graphs Excluding Small Minors

Grohe, Martin and Neuen, Daniel and Wiebking, Daniel
(2020) Isomorphism Testing for Graphs Excluding Small Minors.
In: 2020 IEEE 61st Annual Symposium on Foundations of Computer Science.
Conference: FOCS IEEE Symposium on Foundations of Computer Science

This is the latest version of this item.

[img] Text
gi-excluded-minor-focs-cispa.pdf - Accepted Version

Download (328kB)
Official URL: https://ieeexplore.ieee.org/abstract/document/9317...

Abstract

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.

Available Versions of this Item

  • Isomorphism Testing for Graphs Excluding Small Minors. (deposited 07 May 2021 15:44) [Currently Displayed]

Actions

Actions (login required)

View Item View Item