CISPA
Browse
cispa_all_3398.pdf (321.14 kB)

Isomorphism Testing for Graphs Excluding Small Minors

Download (321.14 kB)
conference contribution
posted on 2023-11-29, 18:15 authored by Martin Grohe, Daniel Neuen, Daniel Wiebking
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.

History

Preferred Citation

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

Primary Research Area

  • Algorithmic Foundations and Cryptography

Name of Conference

IEEE Symposium on Foundations of Computer Science (FOCS)

Legacy Posted Date

2021-05-07

Open Access Type

  • Green

BibTeX

@inproceedings{cispa_all_3398, title = "Isomorphism Testing for Graphs Excluding Small Minors", author = "Grohe, Martin and Neuen, Daniel and Wiebking, Daniel", booktitle="{IEEE Symposium on Foundations of Computer Science (FOCS)}", year="2020", }

Usage metrics

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC