检索结果-内蒙古大学图书馆

The Iteration Number of the weisfeiler-leman algorithm

ACM Transactions on Computational Logic 2025年第1期26卷 1-31页

作者： Grohe, Martin Lichter, Moritz Neuen, Daniel RWTH Aachen University Aachen Germany Max Planck Institute for Informatics Saarbrücken Germany

We prove new upper and lower bounds on the number of iterations the -dimensional weisfeiler-leman algorithm (-WL) requires until stabilization. For , we show that -WL stabilizes after at most iterations (where denotes the number of vertices of the input structures), obtaining the first improvement over the trivial upper bound of and extending a previous upper bound of for .We complement our upper bounds by constructing -ary relational structures on which -WL requires at least iterations to stabilize. This improves over a previous lower bound of .We also investigate tradeoffs between the dimension and the iteration number of WL, and show that -WL, where , can simulate the -WL algorithm using only many iterations, but still requires at least iterations for any (that is sufficiently smaller than ).The number of iterations required by -WL to distinguish two structures corresponds to the quantifier rank of a sentence distinguishing them in the -variable fragment of first-order logic with counting quantifiers. Hence, our results also imply new upper and lower bounds on the quantifier rank required in the logic , as well as tradeoffs between variable number and quantifier rank. © 2025 Copyright held by the owner/author(s).

关键词： weisfeiler-leman algorithm iteration number first-order logic with counting quantifiers

来源：评论

学校读者我要写书评

暂无评论

THE POWER OF THE weisfeiler-leman algorithm TO DECOMPOSE GRAPHS

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2022年第1期36卷 252-298页

作者： Kiefer, Sandra Neuen, Daniel Rhein Westfal TH Aachen Informat 7 D-52062 Aachen Germany CISPA Helmholtz Ctr Informat Secur D-66123 Saarbrucken Germany

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 two-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 nonisomorphic graphs is at most the dimension required to distinguish nonisomorphic 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, Furer, and Immerman, we also provide a new lower bound that is asymptotically tight up to a factor of 2.

关键词： weisfeiler-leman algorithm separators first-order logic counting quantifiers

来源：评论

学校读者我要写书评

暂无评论

The Iteration Number of the weisfeiler-leman algorithm 38

The Iteration Number of the Weisfeiler-Leman Algorithm

引用

38th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)

作者： Grohe, Martin Lichter, Moritz Neuen, Daniel Rhein Westfal TH Aachen Aachen Germany Tech Univ Darmstadt Darmstadt Germany Univ Bremen Bremen Germany

ISBN: (纸本)9798350335873

We prove new upper and lower bounds on the number of iterations the k-dimensional weisfeiler-leman algorithm (k-WL) requires until stabilization. For k >= 3, we show that k-WL stabilizes after at most O(kn(k-1) log n) iterations (where n denotes the number of vertices of the input structures), obtaining the first improvement over the trivial upper bound of n(k) - 1 and extending a previous upper bound of O(n log n) for k = 2 [Lichter et al., LICS 2019]. We complement our upper bounds by constructing k-ary relational structures on which k-WL requires at least n(Omega(k)) iterations to stabilize. This improves over a previous lower bound of n(Omega(k/ log k)) [Berkholz, Nordstr om, LICS 2016]. We also investigate tradeoffs between the dimension and the iteration number of WL, and show that d-WL, where d = inverted right perpendicular 3(k+1)/2 inverted left perpendicular, can simulate the k-WL algorithm using only O(k2 center dot n(left perpendiculark/2right perpendicular+1) log n) many iterations, but still requires at least n(Omega(k)) iterations for any d (that is sufficiently smaller than n). The number of iterations required by k-WL to distinguish two structures corresponds to the quantifier rank of a sentence distinguishing them in the (k + 1)-variable fragment Ck+ 1 of first-order logic with counting quantifiers. Hence, our results also imply new upper and lower bounds on the quantifier rank required in the logic Ck+1, as well as tradeoffs between variable number and quantifier rank.

关键词： weisfeiler-leman algorithm iteration number first-order logic with counting quantifiers quantifier rank

来源：评论

学校读者我要写书评

暂无评论

The weisfeiler-leman algorithm and recognition of graph properties

引用

THEORETICAL COMPUTER SCIENCE 2021年 895卷 96-114页

作者： Fuhlbrueck, Frank Koebler, Johannes Ponomarenko, Ilia Verbitsky, Oleg Humboldt Univ Inst Informat Unter Linden 6 D-10099 Berlin Germany Steklov Inst Math St Petersburg St Petersburg Russia

The k-dimensional weisfeiler-leman algorithm (k-WL) is a very useful combinatorial tool in graph isomorphism testing. We address the applicability of k-WL to recognition of graph properties. Let G be an input graph with n vertices. We show that, if n is prime, then vertex-transitivity of G can be seen in a straightforward way from the output of 2-WL on G and on the vertex-individualized copies of G. This is perhaps the first non-trivial example of using the weisfeiler-leman algorithm for recognition of a natural graph property rather than for isomorphism testing. On the other hand, we show that, if n is divisible by 16, then k-WL is unable to distinguish between vertex-transitive and non-vertex-transitive graphs with n vertices unless k = Omega(root n). Similar results are obtained for recognition of arc-transitivity. Our lower bounds are based on an analysis of the Cai-Furer-Immerman construction, which might be of independent interest. In particular, we provide sufficient conditions under which the Cai-Furer-Immerman graphs can be made colorless. (C) 2021 Elsevier B.V. All rights reserved.

关键词： weisfeiler-leman algorithm Recognition of graph properties Vertex-transitive graphs Arc-transitive graphs Coherent configurations

来源：评论

学校读者我要写书评

暂无评论

IDENTIFIABILITY OF GRAPHS WITH SMALL COLOR CLASSES BY THE weisfeiler-leman algorithm

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2021年第3期35卷 1792-1853页

作者： Fuhlbrueck, Frank Koebler, Johannes Verbitsky, Oleg Humboldt Univ Inst Informat Unter Linden 6 D-10099 Berlin Germany

As is well known, the isomorphism problem for vertex-colored graphs with color multiplicity at most 3 is solvable by the classical two-dimensional weisfeiler-leman algorithm (2-WL). On the other hand, the prominent Cai-Furer-Immerman construction shows that even the multidimensional version of the algorithm does not suffice for graphs with color multiplicity 4. We give an efficient decision procedure that, given a graph G of color multiplicity 4, recognizes whether or not G is identifiable by 2-WL, that is, whether or not 2-WL distinguishes G from every nonisomorphic graph. In fact, we solve the much more general problem of recognizing whether or not a given coherent configuration of maximum fiber size 4 is separable. This extends our recognition algorithm to graphs of color multiplicity 4 with directed and colored edges. Our decision procedure is based on an explicit description of the class of graphs with color multiplicity 4 that are not identifiable by 2-WL. The Cai-Furer-Immerman graphs of color multiplicity 4 distinctly appear here as a natural subclass, which demonstrates that the Cai-Furer-Immerman construction is not ad hoc. Our classification reveals also other types of graphs that are hard for 2-WL. One of them arises from patterns known as (n(3))-configurations in incidence geometry.

关键词： graph isomorphism weisfeiler-leman algorithm Cai-Furer-Immerman graphs coherent configurations

来源：评论

学校读者我要写书评

暂无评论

Identifiability of Graphs with Small Color Classes by the weisfeiler-leman algorithm 37

Identifiability of Graphs with Small Color Classes by the We...

引用

37th International Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Fuehlbrueck, Frank Koebler, Johannes Verbitsky, Oleg Humboldt Univ Inst Informat Berlin Germany

ISBN: (纸本)9783959771405

It is well known that the isomorphism problem for vertex-colored graphs with color multiplicity at most 3 is solvable by the classical 2-dimensional weisfeiler-leman algorithm (2-WL). On the other hand, the prominent Cai-Fiirer-Immerman construction shows that even the multidimensional version of the algorithm does not suffice for graphs with color multiplicity 4. We give an efficient decision procedure that, given a graph G of color multiplicity 4, recognizes whether or not G is identifiable by 2-WL, that is, whether or not 2-WL distinguishes G from any non-isomorphic graph. In fact, we solve the more general problem of recognizing whether or not a given coherent configuration of maximum fiber size 4 is separable. This extends our recognition algorithm to directed graphs of color multiplicity 4 with colored edges. Our decision procedure is based on an explicit description of the class of graphs with color multiplicity 4 that are not identifiable by 2-WL. The Cai-Fiirer-Immerman graphs of color multiplicity 4 distinctly appear here as a natural subclass, which demonstrates that the Cai-Fiirer-Immerman construction is not ad hoc. Our classification reveals also other types of graphs that are hard for 2-WL. One of them arises from patterns known as (n(3))-configurations in incidence geometry.

关键词： Graph Isomorphism weisfeiler-leman algorithm Cai-Furer-Immerman Graphs coherent Configurations

来源：评论

学校读者我要写书评

暂无评论

Walk refinement, walk logic, and the iteration number of the weisfeiler-leman algorithm 19

Walk refinement, walk logic, and the iteration number of the...

引用

Proceedings of the 34th Annual ACM/IEEE Symposium on Logic in Computer Science

作者： Moritz Lichter Ilia Ponomarenko Pascal Schweitzer TU Kaiserslautern Institute of the Russian Academy of Sciences

We show that the 2-dimensional weisfeiler-leman algorithm stabilizes n-vertex graphs after at most O(n log n) iterations. This implies that if such graphs are distinguishable in 3-variable first order logic with counting, then they can also be distinguished in this logic by a formula of quantifier depth at most O(n log n).For this we exploit a new refinement based on counting walks and argue that its iteration number differs from the classic weisfeiler-leman refinement by at most a logarithmic factor. We then prove matching linear upper and lower bounds on the number of iterations of the walk refinement. This is achieved with an algebraic approach by exploiting properties of semisimple matrix algebras. We also define a walk logic and a bijective walk pebble game that precisely correspond to the new walk refinement.

关键词： weisfeiler-leman algorithm

来源：评论

学校读者我要写书评

暂无评论

Walk refinement, walk logic, and the iteration number of the weisfeiler-leman algorithm 34

Walk refinement, walk logic, and the iteration number of the...

引用

34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)

作者： Lichter, Moritz Ponomarenko, Ilia Schweitzer, Pascal TU Kaiserslautern Kaiserslautern Germany Russian Acad Sci St Petersburg Dept Steklov Math Inst Moscow Russia

ISBN: (纸本)9781728136080

We show that the 2-dimensional weisfeiler-leman algorithm stabilizes n-vertex graphs after at most O(n log n) iterations. This implies that if such graphs are distinguishable in 3-variable first order logic with counting, then they can also be distinguished in this logic by a formula of quantifier depth at most O(n log n). For this we exploit a new refinement based on counting walks and argue that its iteration number differs from the classic weisfeiler-leman refinement by at most a logarithmic factor. We then prove matching linear upper and lower bounds on the number of iterations of the walk refinement. This is achieved with an algebraic approach by exploiting properties of semisimple matrix algebras. We also define a walk logic and a bijective walk pebble game that precisely correspond to the new walk refinement.

关键词： first order logic counting quantifiers quantifier depth weisfeiler-leman algorithm

来源：评论

学校读者我要写书评

暂无评论

Cutting Planes Width and the Complexity of Graph Isomorphism Refutations

引用

ACM TRANSACTIONS ON COMPUTATIONAL LOGIC 2024年第4期25卷 1-25页

作者： Toran, Jacobo Woerz, Florian Univ Ulm Inst Theoret Comp Sci Ulm Germany

The width complexity measure plays a central role in resolution and other propositional proof systems like Polynomial Calculus (under the name of degree). The study of width lower bounds is the most used method for proving size lower bounds, and it is known that for the mentioned proof systems, proofs with small width also imply the existence of proofs with small size. Not much has been studied, however, about the width parameter in the cutting planes (CP) proof system, a measure that was introduced by Dantchev and Martin in 2009 under the name of CP cutwidth. In this article, we study the width complexity of CP refutations of graph isomorphism formulas. For a pair of non-isomorphic graphs G and H, we show a direct connection between the weisfeiler-leman differentiation number WL (G, H) of the graphs and the width of a CP refutation for the corresponding isomorphism formula width k, and if WL(G, H) > k, then there are no CP refutations of Iso(G, H) with width k - 2. Similar results are known for other proof systems, like Resolution, Sherali-Adams, or Polynomial Calculus. We also obtain polynomial-length CP refutations from our width bound for isomorphism formulas for graphs with constant weisfeiler-leman dimension. Furthermore, we notice that a length lower bound for refuting graph isomorphism formulas in the subsystem of tree-like cutting planes with polynomially bounded coefficients follows from known results.

关键词： Proof Complexity Cutting Planes Cutwidth Linear Programming weisfeiler-leman algorithm Graph Isomorphism k-Variable Fragment First-Order Counting Logic Hella's Bijective Pebble Game

来源：评论

学校读者我要写书评

暂无评论

Isomorphism Testing for Graphs Excluding Small Topological Subgraphs

引用

ACM TRANSACTIONS ON algorithmS 2024年第3期20卷 1-43页

作者： Neuen, Daniel Univ Bremen Bibliothekstr 5 D-28359 Bremen Germany

We give an isomorphism test that runs in time n polylog (h) on all n-vertex graphs excluding some h-vertex graph as a topological subgraph. Previous results state that isomorphism for such graphs can be tested in time n polylog (n) (Babai, STOC 2016) and nf f (h) for some function f (Grohe and Marx, SIAM J. Comp., 2015). Our result also unifies and extends previous isomorphism tests for graphs of maximum degree d running in time n polylog (d) (SIAM J. Comp., 2023) and for graphs of Hadwiger number h running in time n polylog (h) (SIAM J. Comp., 2023).

关键词： Graph isomorphism topological subgraphs weisfeiler-leman algorithm automorphism groups

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：