The Iteration Number of the Weisfeiler-Leman Algorithm

作     者：Grohe, Martin Lichter, Moritz Neuen, Daniel 

作者机构：RWTH Aachen University Aachen Germany Max Planck Institute for Informatics Saarbrücken Germany 

出 版 物：《ACM Transactions on Computational Logic》 (ACM Trans. Comput. Log.)

年 卷 期：2025年第26卷第1期

页      面：1-31页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：M. Grohe is funded by the European Union (ERC  SymSim  101054974). M. Lichter is also funded by the European Union (ERC  EngageS  820148). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council. Neither the European Union nor the granting authority can be held responsible for them 

主　　题：Weisfeiler-Leman algorithm iteration number first-order logic with counting quantifiers 

摘      要：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).