CISPA
Browse
cispa_all_3508.pdf (502.43 kB)

Isomorphism Testing for Graphs Excluding Small Topological Subgraphs

Download (502.43 kB)
conference contribution
posted on 2023-11-29, 18:19 authored by Daniel Neuen
We give an isomorphism test that runs in time n^{polylog(h)} on all n-vertex graphs excluding some h-vertex graph as a topological subgraph. Previous results state that isomorphism for such graphs can be tested in time n^{polylog(n)} (Babai, STOC 2016) and n^{f(h)} for some function $f$ (Grohe and Marx, SIAM J. Comp., 2015). Our result also unifies and extends previous isomorphism tests for graphs of maximum degree d running in time n^{polylog(d)} (FOCS 2018) and for graphs of Hadwiger number h running in time n^{polylog(h)} (FOCS 2020).

History

Preferred Citation

Daniel Neuen. Isomorphism Testing for Graphs Excluding Small Topological Subgraphs. In: ACM-SIAM Symposium on Discrete Algorithms (SODA). 2022.

Primary Research Area

  • Algorithmic Foundations and Cryptography

Name of Conference

ACM-SIAM Symposium on Discrete Algorithms (SODA)

Legacy Posted Date

2021-12-14

Open Access Type

  • Gold

BibTeX

@inproceedings{cispa_all_3508, title = "Isomorphism Testing for Graphs Excluding Small Topological Subgraphs", author = "Neuen, Daniel", booktitle="{ACM-SIAM Symposium on Discrete Algorithms (SODA)}", year="2022", }

Usage metrics

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC