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 $\Delta$ 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}(\Delta 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.

翻译：组合精炼技术已被证明是一种有效的方法, 用来测试特定类别的图表。 如果精炼周期数量少, 则在低复杂度类中出现相应的异形问题。 我们调查了Circulan 图形中2维维维瑟勒- 莱曼算法的轮复杂度, 即Cayley 图表 $\ mathbb ⁇ n, 并且证明, 稳定之前的轮数由 $\ mathcal{O} (d)\ log n) (d) 美元(n) 复杂度) 约束, 美元是 $n美元 的调值。 具体的结果是, 在 NC 中可以测试2维维维维的Wisfell- Leman 算法, 以美元为奇数, 3$\ 和nexexa $ 小于$。 我们还显示, 彩色精度方法( 也称为 1 维维摄氏- leman caliceal) 的精度方法, 最能化的硬度 的纸质级计算结果。