Abstract 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 two-dimensional Weisfeiler--Leman algorithm on circulant graphs, i.e., on Cayley graphs of the cyclic group $$\mathbb{Z}_n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>Z</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:math> , and prove that the number of rounds until stabilization is bounded by $$\mathcal{O}(d(n)\log n)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mi>d</mml:mi> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> <mml:mo>log</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> , where $$d(n)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>d</mml:mi> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> 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$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mi>p</mml:mi> <mml:mi>ℓ</mml:mi> </mml:msup> </mml:math> with p an odd prime, $$\ell&gt;3$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>ℓ</mml:mi> <mml:mo>&gt;</mml:mo> <mml:mn>3</mml:mn> </mml:mrow> </mml:math> and vertex degree $$\Delta$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>Δ</mml:mi> </mml:math> smaller than p. We also show that the color refinement method (also known as the one-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)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mi>Δ</mml:mi> <mml:mspace/> <mml:mi>n</mml:mi> <mml:mo>log</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> . Moreover, this provides a first example where a sophisticated approach to isomorphism testing put forward by Tinhofer has a real practical meaning.

Laurence Kluge

Computational Complexity

计算复杂性提出了计算复杂性方面的杰出研究。它的主题是数学和理论计算机科学之间的接口，具有清晰的数学轮廓和严格的数学格式。中心主题是：计算模型、复杂性界限（特别强调下界）、复杂性类别、权衡结果用于确定性、概率性和非确定性计算的“一般”（布尔）和“结构化”计算（例如决策树、算术电路）的顺序和并行计算最坏情况和平均情况的具体重点领域包括：复杂性类别的结构（简化、相对化问题、度，去随机化）代数复杂性（双线性复杂性，多项式、组、代数和表示的计算）交互式证明、伪随机生成和随机性提取复杂性问题：密码学学习理论数论逻辑（逻辑理论的复杂性，决策过程的成本）组合优化和近似解分布式计算性能测试。

The journal 'Computational Complexity' is dedicated to outstanding research in the field of computational complexity, focusing on the interface between mathematics and theoretical computer science, characterized by clear mathematical outlines and rigorous mathematical formats. The central themes include computational models, complexity bounds (with a particular emphasis on lower bounds), complexity classes, and trade-off results for deterministic, probabilistic, and non-deterministic computations. Specific areas of focus include: the structure of complexity classes (simplification, relativization problems, degrees, derandomization), algebraic complexity (bilinear complexity, computations of polynomials, groups, algebras, and representations), interactive proofs, pseudorandom generation, and randomness extraction. Complexity issues encompass cryptography, learning theory, number theory, logic (the complexity of logical theories, costs of decision processes), combinatorial optimization and approximate solutions, as well as performance testing in distributed computing.

《Computational Complexity》期刊致力于计算复杂性领域的杰出研究，涵盖数学与理论计算机科学之间的接口，具有清晰的数学轮廓和严格的数学格式。其核心主题包括计算模型、复杂性界限（特别是下界）、复杂性类别，以及用于确定性、概率性和非确定性计算的权衡结果。具体重点领域包括：复杂性类别的结构（简化、相对化问题、度，去随机化）、代数复杂性（双线性复杂性、多项式、组、代数和表示的计算）、交互式证明、伪随机生成和随机性提取。复杂性问题涉及密码学、学习理论、数论、逻辑（逻辑理论的复杂性、决策过程的成本）、组合优化和近似解，以及分布式计算性能测试。

Category	Quartile
计算机科学	3
计算机科学, 计算机理论方法	3
计算机科学, 数学	3

Combinatorial refinement on circulant graphs

ivySCI AI Smartly Parses PDF, Answers Researchers' Questions, and Helps You Understand Papers in Seconds

Journal Info