The Weisfeiler-Leman procedure is a widely-used technique for graph isomorphism testing that works by iteratively computing an isomorphism-invariant coloring of vertex tuples. Meanwhile, a fundamental tool in structural graph theory, which is often exploited in approaches to tackle the graph isomorphism problem, is the decomposition into 2- and 3-connected components. We prove that the 2-dimensional Weisfeiler-Leman algorithm implicitly computes the decomposition of a graph into its 3-connected components. This implies that the dimension of the algorithm needed to distinguish two given non-isomorphic graphs is at most the dimension required to distinguish non-isomorphic 3-connected components of the graphs (assuming dimension at least 2). To obtain our decomposition result, we show that, for k >= 2, the k-dimensional algorithm distinguishes k-separators, i.e., k-tuples of vertices that separate the graph, from other vertex k-tuples. As a byproduct, we also obtain insights about the connectivity of constituent graphs of association schemes. In an application of the results, we show the new upper bound of k on the Weisfeiler-Leman dimension of the class of graphs of treewidth at most k. Using a construction by Cai, F\"urer, and Immerman, we also provide a new lower bound that is asymptotically tight up to a factor of 2.
翻译:Weisfeleler- Leman 程序是一种广泛使用的图形异形测试技术,它通过迭代计算顶部图的异形-异变颜色来运作。同时,结构图形理论的一个基本工具,经常在解决图形偏形问题的方法中加以利用,是分解成2个和3个连接的组件。我们证明,2维Weisfeler-Leman 算法隐含地将一个图形分解成3个连接的组件。这意味着,区分两个给定的非异形图形所需的算法的尺寸,最多是区分图中非异形3个连接的组件(假设至少2个维度)所需的尺寸。为了获得我们的分解结果,我们显示,对于 k ⁇ 2, k- 维度算算法将K- sepreparators, e.e.e., k- 和 k- lex 将图的双色分解成形图与其他 We- tupex ktles.