Computational Complexity of the Weisfeiler-Leman Dimension
ACM Transactions on Computational Logic · 30.04.2026 · 27 (2) · 1-36
DOI: 10.1145/3798282 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Computational Logic, online erschienen am 16.04.2026. Verfasst von Moritz Lichter und 2 weiteren Autor:innen. Die Arbeit nennt 44 Literaturangaben. Gefördert von: H2020 European Research Council, HORIZON EUROPE European Research Council.
Abstract (Originalsprache)
The Weisfeiler-Leman dimension of a graph \( G \) is the least number \( k \) such that the \( k \) -dimensional Weisfeiler-Leman algorithm distinguishes \( G \) from every other non-isomorphic graph, or equivalently, the least \( k \) such that \( G \) is definable in \((k+1)\) -variable logic with counting. The dimension is a standard measure of the descriptive or structural complexity of a graph and recently finds various applications in particular in the context of machine learning. This article studies the complexity of computing the Weisfeiler-Leman dimension. We observe that deciding whether the Weisfeiler-Leman dimension of \( G \) is at most \( k \) is NP -hard, even if \( G \) is restricted to have 4-bounded color classes. Therefore, we study parameterized versions of the problem. For each fixed \(k\geq 2\) , we give a polynomial-time algorithm that decides whether the Weisfeiler-Leman dimension of a given graph with 5-bounded color classes is at most \( k \) . Moreover, we show that for these bounds on the color classes, this is optimal because the problem is P -hard under logspace-uniform AC 0 -reductions. Furthermore, for each larger bound \( c \) on the color classes and each fixed \(k\geq 2\) , we provide a polynomial-time decision algorithm for the abelian case, that is, for structures of which each color class has an abelian automorphism group. While the graph classes we consider may seem quite restrictive, graphs with 4-bounded abelian colors include CFI-graphs and multipedes, which form the basis of almost all known hard instances and lower bounds related to the Weisfeiler-Leman algorithm.
Förderung
- H2020 European Research Council
- HORIZON EUROPE European Research Council
Zitieren
APA
Lichter, M., Raßmann, S., & Schweitzer, P. (2026). Computational Complexity of the Weisfeiler-Leman Dimension. ACM Transactions on Computational Logic, 27(2), 1-36. https://doi.org/10.1145/3798282
Vancouver
Lichter M, Raßmann S, Schweitzer P. Computational Complexity of the Weisfeiler-Leman Dimension. ACM Transactions on Computational Logic. 2026;27(2):1-36. doi:10.1145/3798282
BibTeX
@article{Lichter2026,
author = {Lichter, Moritz and Raßmann, Simon and Schweitzer, Pascal},
title = {Computational Complexity of the Weisfeiler-Leman Dimension},
journal = {ACM Transactions on Computational Logic},
year = {2026},
volume = {27},
number = {2},
pages = {1--36},
doi = {10.1145/3798282}
}
EUVIMED