(2022) Isomorphism Testing for Graphs Excluding Small Topological Subgraphs.
In: UNSPECIFIED.
Conference:
SODA ACM/SIAM Symposium on Discrete Algorithms
|
Text
SODA22-Paper#337.pdf Download (514kB) | Preview |
Official URL: https://doi.org/10.1137/1.9781611977073.59
Abstract
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).
| Item Type: | Conference or Workshop Item (A Paper) (Paper) |
|---|---|
| Divisions: | Dániel Marx (DM) |
| Conference: | SODA ACM/SIAM Symposium on Discrete Algorithms |
| Depositing User: | Daniel Neuen |
| Date Deposited: | 14 Dec 2021 09:52 |
| Last Modified: | 28 Oct 2022 13:12 |
| Primary Research Area: | NRA1: Trustworthy Information Processing |
| URI: | https://publications.cispa.saarland/id/eprint/3508 |
Actions
Actions (login required)
 |
View Item |