2026-07-25T09:51:07Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22770 2025-10-02T11:31:31Z ddc:004 open_access

Computational Complexity of the Weisfeiler-Leman Dimension Lichter, Moritz Raßmann, Simon Schweitzer, Pascal Weisfeiler-Leman algorithm dimension complexity coherent configurations 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 first-order 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 paper 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. For each fixed k ≥ 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 PTIME-hard under logspace-uniform AC_0-reductions. Furthermore, for each larger bound c on the color classes and each fixed k ≥ 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Moritz Lichter and Simon Raßmann and Pascal Schweitzer 2025 Is Part Of LIPIcs, Volume 326, 33rd EACSL Annual Conference on Computer Science Logic (CSL 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CSL.2025.13 urn:nbn:de:0030-drops-227707 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2025.13 eng https://creativecommons.org/licenses/by/4.0/legalcode