论文标题
图形的同构测试不包括小拓扑子图
Isomorphism Testing for Graphs Excluding Small Topological Subgraphs
论文作者
论文摘要
我们给出了一个同构测试，该测试在所有$ n $ -n $ -vertex图上及时运行$ n^{\ perialatorname {polylog}（h）} $，不包括一些$ h $ vertex vertex图作为拓扑子术。先前的结果表明，此类图的同构可以在时间$ n^{\ operatorname {polylog}（n）} $（Babai，Stoc 2016）和$ n^{f（h）} $的某些功能$ f $（Grohe和Marx，Marx，Siam J. Comp。，2015年）的$ N^{f（h）} $。 我们的结果还统一并扩展了以前的同构测试，用于最高度$ d $的图表$ n^{\ propatatorName {polylog}（polylog}（d）} $（siam J. comp。，2023）和hadwiger $ h $ h $ h $ h $ h $ h $ h $ h $ h $ h $ h $ h $ h $ h $ h $ h $ h in time $ n^{\ opporyOrnAme j. {\ opertatorname j.
We give an isomorphism test that runs in time $n^{\operatorname{polylog}(h)}$ on all $n$-vertex graphs excluding some $h$-vertex vertex graph as a topological subgraph. Previous results state that isomorphism for such graphs can be tested in time $n^{\operatorname{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^{\operatorname{polylog}(d)}$ (SIAM J. Comp., 2023) and for graphs of Hadwiger number $h$ running in time $n^{\operatorname{polylog}(h)}$ (SIAM J. Comp., 2023).
