论文标题
除小型未成年人的图形测试的同构测试
Isomorphism Testing for Graphs Excluding Small Minors
论文作者
论文摘要
我们证明，在$ n $ -vertex Graph上，有一个图形同构测试$ n^{\ operatotorname {polylog}（h）} $，不包括一些$ h $ -vertex图作为次要的。以前已知的界限是$ n^{\ peripatorName {poly}（h）} $（Ponomarenko，1988）和$ n^{\ permatatorName {polylog}（n）} $（Babai，STOC 2016）。对于算法，我们结合了组理论图同构机械中的最新进展和新的图理论论点。
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.
