Isomorphism Testing for Graphs Excluding Small Minors

Grohe, Martin; Neuen, Daniel; Wiebking, Daniel

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Paper

Isomorphism Testing for Graphs Excluding Small Minors

MPS-Authors

/persons/resource/persons252640

Neuen, Daniel
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource

No external resources are shared

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

Fulltext (public)

arXiv:2004.07671.pdf
(Preprint), 402KB

Supplementary Material (public)

There is no public supplementary material available

Citation

Grohe, M., Neuen, D., & Wiebking, D. (2020). Isomorphism Testing for Graphs Excluding Small Minors. Retrieved from https://arxiv.org/abs/2004.07671.

Cite as: https://hdl.handle.net/21.11116/0000-0007-9943-1

Abstract

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