论文标题
循环图上的组合精炼
Combinatorial refinement on circulant graphs
论文作者
论文摘要
事实证明，组合精炼技术是针对特定类别类别的同构测试的有效方法。如果精炼弹的数量很少，则将相应的同构问题放在低复杂性类别中。我们调查了循环图上的二维WEISFEILER-LEMAN算法的圆形复杂性，即在周期性组$ \ Mathbb {Z} _n $的cayley图上，并证明圆的数量直到稳定为$ \ m nogscal {o} $ d（n）$ d（n）$ d（n）$ d（n）$ d（n） $ n $。尤其是，可以在NC中测试同构的订单循环图$ p^\ ell $，$ p $ a奇数，$ \ ell> 3 $和vertex guger $δ$小于$ p $。 我们还表明，在两个适当选择的顶点个性化之后，每个非平凡的循环图的颜色改进方法（也称为一维Weisfeiler-Leman算法）计算每个非平凡循环图的规范标记。因此，此类图的规范标记问题最多具有与颜色改进相同的复杂性，这导致$ \ Mathcal {O}（Δn\ log n）$的时间结合。此外，这提供了第一个示例，在该示例中，Tinhofer提出的同构测试的复杂方法具有真正的实际含义。
The combinatorial refinement techniques have proven to be an efficient approach to isomorphism testing for particular classes of graphs. If the number of refinement rounds is small, this puts the corresponding isomorphism problem in a low-complexity class. We investigate the round complexity of the 2-dimensional Weisfeiler-Leman algorithm on circulant graphs, i.e. on Cayley graphs of the cyclic group $\mathbb{Z}_n$, and prove that the number of rounds until stabilization is bounded by $\mathcal{O}(d(n)\log n)$, where $d(n)$ is the number of divisors of $n$. As a particular consequence, isomorphism can be tested in NC for connected circulant graphs of order $p^\ell$ with $p$ an odd prime, $\ell>3$ and vertex degree $Δ$ smaller than $p$. We also show that the color refinement method (also known as the 1-dimensional Weisfeiler-Leman algorithm) computes a canonical labeling for every non-trivial circulant graph with a prime number of vertices after individualization of two appropriately chosen vertices. Thus, the canonical labeling problem for this class of graphs has at most the same complexity as color refinement, which results in a time bound of $\mathcal{O}(Δn\log n)$. Moreover, this provides a first example where a sophisticated approach to isomorphism testing put forward by Tinhofer has a real practical meaning.
