Computational complexity of the Weisfeiler-Leman dimension

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 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. Therefore, we study parameterized versions of the problem. 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 P -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.