Computational Complexity of the Weisfeiler-Leman Dimension

We extend the results of [15] from $2$-$\mathrm{WL}$ to $k$-$\mathrm{WL}$ and give a polynomial-time algorithm deciding whether a graph with $5$-bounded color classes is identified by $k\text{-}\mathrm{WL}$:

Via the correspondence of $k$-$\mathrm{WL}$ to $(k+1)$-variable counting logic, Theorem 1 implies that definability of graphs with $5$-bounded color classes in this logic is decidable in polynomial time. While the restriction to $5$-bounded color classes may seem stark, almost all known hardness results and lower bounds for the Weisfeiler-Leman algorithm remain true for graphs with bounded color classes and in most cases even $4$-bounded color classes suffice [19, 13, 40, 39, 38].

Towards generalizing Theorem 1 to arbitrary relational structures and larger color classes, we consider structures with abelian color classes, i.e., structures of which each color class induces a structure with an abelian automorphism group. Such structures were previously considered in the context of descriptive complexity theory [44], and include both CFI-graphs [11] and multipedes [39, 38] over ordered base graphs, which form the basis of all known constructions of graphs with high Weisfeiler-Leman dimension. For many cases in descriptive complexity theory, restricting to $4$-bounded abelian color classes is sufficient, but in some cases larger (but still abelian) color classes are required [26, 18, 33, 34]. For such structures, we obtain a polynomial-time algorithm as before:

On the side of hardness results, we first prove that when the dimension $k$ is part of the input, the identification problem is NP-hard. Note that a similar result was recently independently observed by Seppelt [42].

Furthermore, we extend the P-hardness results for $1$-$\mathrm{WL}$ [2] to arbitrary $k$ and prove that, when $k$ is fixed, the $k$-$\mathrm{WL}$-identification problem is hard for polynomial time:

To prove Theorem 1, we exploit the close connection between the coloring computed by $k$-$\mathrm{WL}$ and certain combinatorial structures called $k$-ary coherent configurations. These structures come with two notions of isomorphisms, algebraic ones and combinatorial ones. Similarly to [15], we reduce the $k$-$\mathrm{WL}$-identification problem to the separability problem for $k$-ary coherent configurations, that is, to decide whether algebraic and combinatorial isomorphisms for a given $k$-ary coherent configuration coincide. We make two crucial observations: First, we show that the $k$-ary coherent configurations obtained from graphs are fully determined by their underlying $2$-ary configurations. We call such configurations $2$-induced. Second, we reduce the separability problem for arbitrary $k$-ary coherent configurations to the same problem on the structurally simpler class of star-free $k$-ary coherent configurations. Combining both observations, we show that two $2$-induced, star-free $k$-ary coherent configurations obtained from $k$-$\mathrm{WL}$-equivalent graphs must be isomorphic. Given such a $k$-ary coherent configuration obtained from a graph, it thus suffices to decide whether there is another non-isomorphic graph yielding the same configuration. Finally, we solve this problem by encoding it into the graph isomorphism problem for structures with bounded color classes, which is polynomial-time solvable [6, 16].

The main obstacle to generalize Theorem 1 to larger color classes or relational structures of higher arity is the existence of $k$-$\mathrm{WL}$-equivalent structures that yield non-isomorphic star-free $k$-ary coherent configurations, which greatly increases the space of possibly equivalent but non-isomorphic structures. To make up for this, we consider structures with abelian color classes. Using both the bijective pebble game [26] and ideas from the theory of coherent configurations, we provide structural insights for the class of $k$-ary coherent configurations with abelian fibers. This allows us to finally prove that in the abelian case, it does suffice to consider other relational structures yielding the same $k$-ary coherent configuration.

NP-hardness in Theorem 3 is proved by combining the known relationship between the Weisfeiler-Leman dimension of CFI-graphs [11] and the tree-width of the underlying base graphs with the recent result that computing the tree-width of cubic graphs is NP-hard [9]. With the same techniques, we can also prove that deciding $k$-$\mathrm{WL}$-equivalence of graphs is co-NP-hard when the dimension $k$ is considered part of the input.

For the P-hardness result of the $k$-$\mathrm{WL}$-identification problem in Theorem 4, we adapt a construction by Grohe [19] that he used to prove P-hardness of the $k$-$\mathrm{WL}$-equivalence problem. The construction encodes monotone boolean circuits into graphs using different types of gadgets. This simultaneously reduces the monotone circuit value problem, which is known to be hard for polynomial time, to the $k$-$\mathrm{WL}$-equivalence and the $k$-$\mathrm{WL}$-identification problem. The main difficulty was to show identification of Grohe’s gadgets, specifically his so-called one-way switches. We give an alternative construction of these one-way switches based on the CFI-construction. This construction simplifies proofs and more importantly yields graphs with $4$-bounded color classes for every $k$. This shows hardness for the $k$-$\mathrm{WL}$-equivalence and $k$-$\mathrm{WL}$-identification problems even for graphs with $4$-bounded abelian color classes.

Full proofs of all statements can be found in the full version of this paper [35].

For $n\in \mathbb{N}$, we set $[n]≔\{1,\mathrm{\dots },n\}$. For a set $A$, the set of all $k$-element subsets of $A$ is denoted by $\left(\genfrac{}{}{0pt}{}{A}{k}\right)$. For two runtime-bounding functions $f$ and $g$ with parameters including $\kappa$, we write $f\in O_{\kappa }(g)$ if $f/g$ is bounded by a function of $\kappa$. A simple graph is a pair $G=(V(G),E(G))$ of a set $V(G)$ of vertices and a set $E(G)\subseteq \left(\genfrac{}{}{0pt}{}{V(G)}{2}\right)$ of undirected edges. For a directed graph, we allow $E(G)\subseteq V{(G)}^2\setminus \{(v,v):v\in V(G)\}$. For either graph type, we write $uv$ for the edge $\{u,v\}$ or $(u,v)$ respectively. For a simple or directed graph $G$, a vertex-coloring of $G$ is a map $\chi :V(G)\to C$ for some finite, ordered set $C$ of colors. Similarly, an edge-coloring is a map $\eta :E(G)\to C$. A (vertex-)color class is a set ${\chi }^{-1}(c)$ for some vertex color $c\in C$. If all color classes have order at most $q$, we say that the colored graph $(G,\chi )$ has $q$-bounded color classes.

Relational structures are a higher-arity analogue of graphs. Formally, a $k$-ary relational structure $𝔄$ is a tuple $(V(𝔄),R_1,\mathrm{\dots },R_{\mathrm{\ell }})$ of vertices $V(𝔄)$ and relations $R_i\subseteq V{(𝔄)}^{r_i}$ with $r_i\le k$. The number $r_i$ is the arity of the relation $R_i$. We again allow relational structures to come with a vertex-coloring and define $q$-bounded color classes as before.

An isomorphism between graphs $G$ and $H$ is a bijection $\phi :V(G)\to V(H)$ such that $uv\in E(G)$ if and only if $\phi (u)\phi (v)\in E(H)$. In this case $G$ and $H$ are isomorphic and we write $G\cong H$. An isomorphism between edge- or vertex-colored graphs must also preserve the vertex- and edge-colors. Similarly, an isomorphism between (vertex-colored) relational structures is a (color-preserving) bijection between the vertex sets that preserves all relations and their complements. An automorphism is an isomorphism from a structure to itself. We say that a graph or relational structure $𝔄$ has abelian color classes if for every color class $C$, the induced substructure $𝔄[C]$ has an abelian automorphism group.

First-order counting logic $\mathrm{C}$ is the extension of first-order logic by the counting quantifiers ${\exists }^{\ge k}$ for all natural numbers $k$, which state that there exist at least $k$ distinct elements satisfying the formula that follows. But because first-order logic has the ability to simulate the counting quantifier ${\exists }^{\ge k}$ by a sequence of $k$ usual existential quantifiers, adding counting quantifiers does not actually increase the expressive power of first-order logic. This situation changes when we restrict the number of variables. For a natural number $k\ge 2$, we define $k$-variable counting logic ${\mathrm{C}}^k$ to be the fragment of $\mathrm{C}$ which only uses the variables $x_1,\mathrm{\dots },x_k$. In order to not restrict the expressive power of these logics too much, we do, however, allow requantifications, that is, quantifications over a variable within the scope of another quantification over the same variable. As an example, the following is a ${\mathrm{C}}^2$-formula

which states that every vertex is adjacent to a vertex of degree $5$.

A relational structure $𝔄$ is definable in ${\mathrm{C}}^k$ if there exists some formula $\phi \in {\mathrm{C}}^k$ which is satisfied by a structure if and only if it is isomorphic to $𝔄$.

The distinguishing power of bounded variable counting logics has another characterization in terms of the Weisfeiler-Leman algorithm. For every $k\ge 2$, the $k$-dimensional Weisfeiler-Leman algorithm ($k$-$\mathrm{WL}$) computes an isomorphism-invariant coloring of $k$-tuples of vertices of a given graph $G$ via an iterative refinement process. Initially, the algorithm colors each $k$-tuple according to its isomorphism type, i.e., $𝐱=(x_1,\mathrm{\dots },x_k),𝐲=(y_1,\mathrm{\dots },y_k)\in V{(G)}^k$ get the same color if and only if mapping $x_i\mapsto y_i$ for every $i\in [k]$ is an isomorphism of the induced subgraphs $G[\{x_1,\mathrm{\dots },x_k\}]$ and $G[\{y_1,\mathrm{\dots },y_k\}]$. In each iteration, this coloring is refined as follows: if ${\chi }_r^G:V{(G)}^k\to C_r$ is the coloring obtained after $r$ refinement rounds, the coloring ${\chi }_{r+1}^G:V{(G)}^k\to C_{r+1}$ is defined as ${\chi }_{r+1}^G(𝐱)≔({\chi }_r^G(𝐱),M_{𝐱}^r)$, where

and $𝐱\frac{y}{i}$ denotes the tuple obtained from $𝐱$ by replacing the $i$-th entry by $y$. If ${\chi }_{r+1}^G$ does not induce a finer color partition on $V{(G)}^k$ than ${\chi }_r^G$, then the algorithm terminates and returns the stable coloring ${\chi }_{\mathrm{\infty }}^G≔{\chi }_{r+1}^G$. This must happen before the $n^k$-th refinement round.

We say that $k$-$\mathrm{WL}$ distinguishes two $k$-tuples $𝐱,𝐲\in V{(G)}^k$ if ${\chi }_{\mathrm{\infty }}^G(𝐱)\ne {\chi }_{\mathrm{\infty }}^G(𝐲)$ and that $k$-$\mathrm{WL}$ distinguishes two $\mathrm{\ell }$-tuples $𝐱,𝐲\in V{(G)}^{\mathrm{\ell }}$ for if $k$-$\mathrm{WL}$ distinguishes the two $k$-tuples we get by repeating the last entries of $𝐱$ respectively $𝐲$. In either case, we write $(G,𝐱){\not\equiv }_{k\text{-}\mathrm{WL}}(G,𝐲)$. Finally, $k$-$\mathrm{WL}$ distinguishes two graphs $G$ and $H$ if the multisets of stable colors computed for the $k$-tuples of vertices over the two graphs disagree. Otherwise, $G$ and $H$ are $k$-$\mathrm{WL}$-equivalent and we write $G{\equiv }_{k\text{-}\mathrm{WL}}H$. A graph $G$ is identified by $k$-$\mathrm{WL}$ if $k$-$\mathrm{WL}$ distinguishes $G$ from every other non-isomorphic graph. Every $n$-vertex graph is identified by $n$-$\mathrm{WL}$, and the least number $k$ such that $k$-$\mathrm{WL}$ identifies $G$ is called the Weisfeiler-Leman dimension of $G$, denoted by $\mathrm{WL}-\dim (G)$.

$k$-$\mathrm{WL}$ is at least as powerful in distinguishing graphs as $(k-1)$-$\mathrm{WL}$ and this hierarchy does not collapse [11]. Completely analogously, $k$-$\mathrm{WL}$ can be applied to relational structures.

In particular, the Weisfeiler-Leman dimension of a structure is precisely one less than the number of variables needed to define the structure in first-order counting logic.

For an introduction to ($2$-ary) coherent configurations and their connection to the Weisfeiler-Leman algorithm we refer to [15]. For $k\ge 2$, a $k$-ary rainbow is a pair $(V,ℛ)$ of a finite set of vertices $V$ and a partition $ℛ$ of $V^k$, whose elements are called basis relations, that satisfies the following two conditions:

(R1)

For every basis relations $R\in ℛ$, all tuples $𝐱,𝐲\in R$ have the same equality type, i.e., $x_i=x_j$ if and only if $y_i=y_j$. We also call this the equality type of the relation $R$.

(R2)

$ℛ$ is closed under permuting indices: For all basis relations $R\in ℛ$ and permutations $\sigma$ of $[k]$, the set $R^{\sigma }≔\{(x_{\sigma (1)},\mathrm{\dots },x_{\sigma (k)}):(x_1,\mathrm{\dots },x_k)\in R\}$ is a basis relation.

Because the vertex set $V$ is determined by the partition $ℛ$, we write $ℛ$ to denote the rainbow $(V,ℛ)$ and in this case write $V(ℛ)$ for its vertex set $V$. A $k$-ary coherent configuration is a $k$-ary rainbow $𝒞$ that is stable under $k$-$\mathrm{WL}$-refinement. Formally, this means that

(C)

for all basis relations $R,R_1,\mathrm{\dots },R_k\in 𝒞$, the intersection number

$$p(R;R_1,\mathrm{\dots },R_k)≔\left|\{y\in V(𝒞):𝐱\frac{y}{i}\in R_i\text{ for all }i\in [k]\}\right|$$

is the same for all choices of $𝐱\in R$ and is thus well-defined.

For $\mathrm{\ell }\le k$, the partition of $k$-vertex tuples of an $\mathrm{\ell }$-ary relational structure according to their isomorphism type always yields a $k$-ary rainbow. The connection of $k$-$\mathrm{WL}$ and $k$-ary coherent configurations is that the partition of $k$-vertex tuples of a graph according to their $k$-$\mathrm{WL}$-colors always forms a $k$-ary coherent configuration.

If $ℛ$ is an $\mathrm{\ell }$-ary rainbow for $\mathrm{\ell }\le k$, we can interpret $ℛ$ as the $k$-ary rainbow $ℛ{|}^k$ by partitioning $k$-tuples according to the basis relations of the $\mathrm{\ell }$-subtuples they contain. Formally, let ${\sim }_{ℛ}$ be the equivalence relation on $V{(ℛ)}^{\mathrm{\ell }}$ whose equivalence classes are the basis relations of $ℛ$. We define the equivalence relation ${\sim }_{ℛ}^k$ on $V{(ℛ)}^k$ by writing $𝐱{\sim }_k𝐲$ if and only if for all $I\in \left(\genfrac{}{}{0pt}{}{[k]}{\mathrm{\ell }}\right)$ we have ${𝐱|}_I{\sim }_{ℛ}{𝐲|}_I$, where ${𝐱|}_I$ is the subtuple of $𝐱$ for which all indices not in $I$ are deleted. The basis relations of $ℛ{|}^k$ are the equivalence classes of ${\sim }_{ℛ}^k$.

For every $k$-ary rainbow $ℛ$, there is a unique coarsest $k$-ary coherent configuration ${\mathrm{WL}}_k(ℛ)$ that is at least as fine as $ℛ$ and is called the $k$-ary coherent closure of $ℛ$. For an $\mathrm{\ell }\le k$ and an $\mathrm{\ell }$-ary rainbow $ℛ$, we also write ${\mathrm{WL}}_k(ℛ)$ for ${\mathrm{WL}}_k(ℛ{|}^k)$. Similarly, for an $\mathrm{\ell }$-ary relational structure $𝔄$, we write ${\mathrm{WL}}_k(𝔄)$ for the partition of $V{(𝔄)}^k$ into $k\text{-}\mathrm{WL}$-color classes.

Every $k$-ary coherent configuration $𝒞$ induces the $\mathrm{\ell }$-ary coherent configuration ${𝒞|}_{\mathrm{\ell }}$ for every $\mathrm{\ell }\le k$ by considering the partition of tuples of the form $(x_1,\mathrm{\dots },x_{\mathrm{\ell }},\mathrm{\dots },x_{\mathrm{\ell }})\in V{(𝒞)}^k$. This $\mathrm{\ell }$-ary coherent configuration is called the $\mathrm{\ell }$-skeleton of $𝒞$. For every basis relation $R\in 𝒞$ and every subset $I\in \left(\genfrac{}{}{0pt}{}{[k]}{\mathrm{\ell }}\right)$ of the indices, the set $R_I≔\{𝐱{|}_I:𝐱\in R\}$ is a basis relation of ${𝒞|}_{\mathrm{\ell }}$ and called the $I$-face of $R$. The $1$-skeleton yields a partition of $V(𝒞)$, whose partition classes are called fibers. We denote the set of fibers by $F(𝒞)$. $𝒞$ has $c$-bounded fibers if all fibers of $𝒞$ have order at most $c$. If $W\subseteq V(𝒞)$ is a union of fibers, the induced structure $𝒞[W]$ is again a $k$-ary coherent configuration. Between two fibers $X$ and $Y$, the induced configuration ${𝒞|}_2$ further induces a partition ${𝒞|}_2[X,Y]$ of $X\times Y$, called an interspace.

A $k$-ary coherent configuration $𝒞$ is $\mathrm{\ell }$-induced if it is the coherent closure of its $\mathrm{\ell }$-skeleton, i.e., if $𝒞={\mathrm{WL}}_k({𝒞|}_{\mathrm{\ell }})$. This is equivalent to $𝒞$ being the coherent closure of some $\mathrm{\ell }$-ary rainbow. In particular, the $k$-ary coherent closure of a (directed, colored) graph is $2$-induced and the $k$-ary coherent closure of an $\mathrm{\ell }$-ary relational structure is $\mathrm{\ell }$-induced for every $k\ge \mathrm{\ell }$.

For a $k$-ary rainbow $ℛ=(V,\{R_1,\mathrm{\dots },R_{\mathrm{\ell }}\})$, the vertex-colored $k$-ary relational structure $(V,R_1,\mathrm{\dots },R_{\mathrm{\ell }},\chi )$ where $\chi$ maps every vertex to its fiber is a colored variant of $ℛ$. Note that this requires choosing an ordering of the basis relations; colored variants are thus not unique.

There are two notions of isomorphism for two $k$-ary coherent configurations $𝒞$ and $𝒟$. First, a combinatorial isomorphism is a bijection $\phi :V(𝒞)\to V(𝒟)$ that preserves the partition into basis relations, i.e., for every basis relation $R\in 𝒞$, the mapped set $R^{\phi }≔\{(\phi (x_1),\mathrm{\dots },\phi (x_k)):(x_1,\mathrm{\dots },x_k)\in R\}$ is a basis relation of $𝒟$. Combinatorial isomorphisms are thus isomorphisms between certain colored variants of $𝒞$ and $𝒟$ and the notion also applies to rainbows.

Second, an algebraic isomorphism is a map $f:𝒞\to 𝒟$ between the two partitions that preserves the intersection numbers. More formally, we require that

(A1)

for all $R\in 𝒞$, the relations $R$ and $f(R)$ have the same equality type,

(A2)

for all $R\in 𝒞$ and permutations $\sigma$ of $[k]$, we have $f(R^{\sigma })=f{(R)}^{\sigma }$, and

(A3)

for all $R,T_1,\mathrm{\dots },T_k\in 𝒞$, we have $p(R;T_1,\mathrm{\dots },T_k)=p(f(R);f(T_1),\mathrm{\dots },f(T_k))$,

but Property (A3) already implies the former two. Algebraic isomorphisms can be thought of as maps preserving the Weisfeiler-Leman colors and thus as a functional perspective on Weisfeiler-Leman equivalence. More formally, if for $k$-ary relational structures $𝔄$ and $𝔅$, $f:{\mathrm{WL}}_k(𝔄)\to {\mathrm{WL}}_k(𝔅)$ is an algebraic isomorphism that preserves the relations of $𝔄$ and $𝔅$, then $f$ is the unique map that maps every color class of the stable coloring computed by $k$-$\mathrm{WL}$ on $𝔄$ to the corresponding color class of the stable coloring computed by $k$-$\mathrm{WL}$ on $𝔅$. In particular, we get $𝔄{\equiv }_{k\text{-}\mathrm{WL}}𝔅$ in this case.

If $f:𝒞\to 𝒟$ is an algebraic isomorphism, then $f$ induces an algebraic isomorphism ${f|}_{\mathrm{\ell }}:{𝒞|}_{\mathrm{\ell }}\to {𝒟|}_{\mathrm{\ell }}$ for every $\mathrm{\ell }\le k$. If $𝒞={\mathrm{WL}}_k(ℛ)$ for some rainbow $ℛ$, $f$ induces a map ${f|}_{ℛ}:ℛ\to {ℛ}^f$ for some rainbow ${ℛ}^f$ by sending each basis relation of $ℛ$, which is a union of basis relations of $𝒞$, to the union of $f$-images of these basis relations of $𝒞$. A combinatorial (respectively algebraic) automorphism of $𝒞$ is a combinatorial (respectively algebraic) isomorphism from $𝒞$ to itself. Every combinatorial isomorphism induces an algebraic isomorphism, but the converse is not true. Algebraic isomorphisms behave nicely with coherent closures as seen in the next lemma (the proof is analogue to the $k=2$ case [15, Lemma 2.4]):

A $k$-ary coherent configuration $𝒞$ is called separable if every algebraic isomorphism $f:𝒞\to 𝒟$ from $𝒞$ is induced by a combinatorial one. There is a close relation to the power of the Weisfeiler-Leman algorithm (the proof is analogue to the $k=2$ case [15, Theorem 2.5]):

Let $𝒞$ be a $k$-ary coherent configuration and $X,Y\in F(𝒞)$ two distinct fibers. A disjoint union of stars between $X$ and $Y$ is a basis relation $S\in {𝒞|}_2[X,Y]$ such that every vertex in $Y$ is incident to exactly one edge in $S$. If no interspace of $𝒞$ contains a disjoint union of stars, then $𝒞$ is called star-free. We show that the separability problem of ($2$-induced) $k$-ary coherent configurations reduces to that of star-free ones.

Let ${\mathrm{𝖤𝗊}}_S$ be the set of pairs of vertices in $Y$ that have a common $S$-neighbor in $X$. We show that the $k$-ary coherent configuration $𝒞$ is uniquely determined by the configuration $𝒞\setminus X$ and the relation ${\mathrm{𝖤𝗊}}_S$. For this, consider the function ${\nu }_S:Y\to X$ that maps each vertex in $Y$ to its unique neighbor in $X$. When we apply this map to some of the $Y$-components of a basis relation $R\in 𝒞$, the resulting set is again a basis relation, and we can obtain every basis relation of $R\in 𝒞$ from basis relations in $𝒞\setminus X$ in this way.

We show that both algebraic and combinatorial isomorphisms can detect the uniqueness of this extension in the following sense: every algebraic or combinatorial isomorphism $𝒞\setminus X\to 𝒟$ uniquely extends to an algebraic or combinatorial isomorphism $𝒞\to {𝒟}^{\ast }$, for some uniquely determined extension ${𝒟}^{\ast }\supseteq 𝒟$ by a single fiber. Hence, $𝒞$ is separable if and only if $𝒞\setminus X$ is. By analyzing this unique extension, it is moreover clear that it does not affect $2$-inducedness. $◀$ Lemma 8 allows us to remove fibers that are incident to a disjoint unions of stars without affecting the separability. This simultaneously generalizes the elimination of interspaces containing a matching and the elimination of fibers of size $2$ from [15].

In order to structurally understand $2$-induced $k$-ary coherent configurations, it mostly suffices to understand their $2$-skeletons. The possible isomorphism types of $2$-ary coherent configurations on a single fiber of order at most $5$ are known [15, 41], see Figure 1. Further, the possible interspaces between fibers of order up to $4$ are also known [15]. For fibers $X,Y\in F(𝒞)$, it is always possible that the interspace $𝒞[X,Y]$ is uniform, meaning that it consists of only a single basis relation $X\times Y$. Every interspace between a fiber of size $5$ and a fiber of size at most $4$ is uniform [15, Lemma 3.1], and every interspace between two fibers of size $5$ is either uniform or contains a matching [15, Section 13]. Now, only two possible non-uniform, star-free interspaces remain, which are depicted in Figure 2.

We call an algebraic automorphism $f$ of a $k$-ary coherent configuration $𝒞$ strict if it fixes every fiber, i.e., it satisfies $f(X)=X$ for every $X\in F(𝒞)$. The strict algebraic automorphisms of $𝒞$ form a group, which we denote by $𝔸(𝒞)$. Using the enumeration of fiber and interspace types, we obtain the following reformulation of separability as in [15, Lemma 7.2].

The forward implication is immediate. For the backward implication, consider an algebraic isomorphism $f:𝒞\to 𝒟$. Because every coherent configuration of order at most $8$ is separable [15], $f$ is induced by a combinatorial isomorphism on every union of two fibers. We pick such a combinatorial isomorphism inducing ${f|}_2$ for every interspace of type $C_8$ and everywhere else, we pick combinatorial isomorphisms inducing ${f|}_2$ just on each fiber. Using the structure of fibers of order at most $5$ and their interspaces, we can show that these isomorphisms combine to a combinatorial isomorphism $\phi$ inducing ${f|}_2$ on every fiber. But then, ${{\phi }^{-1}\circ f|}_2$ is a strict algebraic automorphism and is thus induced by a combinatorial automorphism $\theta$. But then, $\phi \circ \theta$ induces ${f|}_2$ and thus also $f$ by Lemma 6. $◀$

We now sketch a polynomial-time algorithm that decides whether every strict algebraic automorphism of a $k$-ary coherent configuration is induced by a combinatorial automorphism. We will heavily use that the graph isomorphism problem is polynomial-time solvable for graphs with bounded color classes.

By encoding the algebraic structure of a coherent configuration $𝒞$ into a relational structure, we obtain the following:

We construct a $(k+1)$-ary relational structure ${𝔄}_{𝒞}$ with $c^k$-bounded color classes such that $\mathrm{Aut}({𝔄}_{𝒞})\cong 𝔸(𝒞)$. The vertices of our constructed structure are the basis relations of $𝒞$, and we color each $(k+1)$-tuple $(R,R_1,\mathrm{\dots },R_k)$ of basis relations using the color $p(R;R_1,\mathrm{\dots },R_k)$. Further, we color each basis relation by the tuple of fibers of its components. Because every fiber is $c$-bounded, at most $c^k$ basis relations can share a color. Furthermore, it is immediate that the automorphisms of the structure constructed so far naturally correspond to strict algebraic automorphisms of $𝒞$. Thus, we can compute a generating set for the group of strict algebraic automorphisms in the required time using Lemma 10. $◀$ Similarly, we can reduce the question whether a strict algebraic automorphism is induced by a combinatorial one to the graph isomorphism problem.

Let $ℭ$ be an arbitrary colored variant of $𝒞$ and ${ℭ}^f$ another colored variant such that $f$ is a color-preserving map between the color classes of $ℭ$ and ${ℭ}^f$. Combinatorial automorphisms inducing $f$ correspond to isomorphisms between $ℭ$ and ${ℭ}^f$, meaning that $f$ is induced by a combinatorial automorphism if and only if $ℭ\cong {ℭ}^f$. As $𝒞$ has bounded fibers, so does $ℭ$. Thus, we can decide the latter in the required time by Lemma 10. $◀$

Those strict algebraic automorphisms that are induced by combinatorial ones form a subgroup of the group of all strict algebraic automorphisms. Hence, it suffices to compute a generating set of the whole group via Lemma 11 and to decide whether all elements of it are induced by combinatorial automorphisms using Lemma 12. $◀$ Finally, we are ready to prove our first theorem. See 1

In a first step, we run $k\text{-}\mathrm{WL}$ on $G$ to get the $2$-induced configuration $𝒞≔{\mathrm{WL}}_k(G)$. By Lemma 7, it remains to decide whether $𝒞$ is separable. Now, we eliminate disjoint unions of stars using Lemma 8, while maintaining $2$-inducedness of $𝒞$. By Lemma 9, it remains to decide whether every strict algebraic automorphism is induced by a combinatorial one. This can be achieved using Corollary 13.

If this is the case, the input structure is identified by $k$-$\mathrm{WL}$. Otherwise, the algorithm actually finds a strict algebraic automorphism $f$ which is not induced by a combinatorial automorphism. By adding back all interspaces containing a disjoint union of stars, we can extend $f$ to an algebraic isomorphism $\widehat{f}:{\mathrm{WL}}_k(G)\to 𝒟$ which is not induced by a combinatorial isomorphism. But then, we can obtain a witnessing graph $H$ from $G$ by replacing its edge set by its ${\widehat{f}|}_2$-image and similarly translating vertex- and edge-colors along $\widehat{f}$. $◀$

To start, we translate the concept of abelian color classes to the corresponding concept of abelian fibers for $k$-ary coherent configurations. A combinatorial automorphism $\phi$ of a $k$-ary coherent configuration $𝒟$ is color-preserving if $\phi$ fixes every basis relation of $𝒟$. This is equivalent to $\phi$ being an automorphism of every colored variant of $𝒟$ or to the algebraic automorphism induced by $\phi$ being the identity (recall that combinatorial automorphisms are not required to fix every basis relation, but only the partition of $V{(𝒟)}^k$ into basis relations). We say that a coherent configuration $𝒞$ has abelian fibers if, for each fiber $X\in F(𝒞)$, the group of color-preserving combinatorial automorphisms of $𝒞[X]$ is abelian.

We start with a structural lemma, which states that small abelian fibers are always thin. For a fiber $X\in F(𝒞)$, a binary basis relation $S\in {𝒞|}_2[X]$ is called thin if every vertex in $X$ is incident to exactly one ingoing and exactly one outgoing $S$-edge, that is, if $S$ is either a matching or a union of directed cycles. The fiber $X$ is called thin if all basis relations $R\in {𝒞|}_2[X]$ are thin and if this is true for all fibers of $𝒞$, we say that $𝒞$ has thin fibers.

Let $X\in F(𝒞)$ be an abelian fiber of order at most $k$. Then ${𝒞|}_2[X]$ is the partition of $X^2$ into orbits under the natural action of the group of color-preserving automorphisms.

Now, assume that some binary basis relation $S\in {𝒞|}_2[X]$ contains two pairs $xy$ and $x{y}^{\prime }$ for $x,y,y^{\prime }\in X$. This implies that there is a color-preserving automorphism $\phi$ of $𝒞[X]$ that maps $xy$ to $x{y}^{\prime }$. But as the group of color-preserving automorphism of $𝒞[X]$ is abelian and acts transitvely on the vertices of $X$, its point-stabilizers are trivial. Because $\phi (x)=x$, this implies $\phi ={\mathrm{id}}_X$ and thus $y^{\prime }=\phi (y)=y$. Thus, the basis relation $S$ is thin. $◀$

Next, we need one well-known lemma on the structure of thin fibers, which essentially states that thin fibers correspond to Cayley graphs of their automorphism groups.

Next, we show that $k$-ary coherent configurations with few, thin fibers are separable:

Let $𝐱\in V{(𝒞)}^k$ be a $k$-tuple of vertices which contains a vertex from every fiber of $𝒞$. Then every vertex of $𝒞$ is the unique outgoing neighbor of some vertex in $𝐱$ with respect to some thin basis relation. Thus, all vertices of $𝒞$ are fixed relative to $𝐱$.

Now, let $ℭ$ be a colored variant of $𝒞$. By Lemma 7, $𝒞$ is separable if and only if $ℭ$ is identified by $k$-$\mathrm{WL}$. We show the latter using the bijective $(k+1)$-pebble game, which is an Ehrenfeucht-Fraïssé-type game capturing $k$-$\mathrm{WL}$-equivalence [26]. Indeed, if $ℭ{\equiv }_{k\text{-}\mathrm{WL}}𝔇$, this corresponds to Duplicator having a winning strategy in this game. But because we can fix every vertex of $ℭ$ by only fixing one vertex per color class, we can easily extract an isomorphism $ℭ\to 𝔇$ from such a winning strategy. $◀$ Finally, we are ready to once again reduce the question of separability to only strict algebraic automorphisms, which we can again deal with using Corollary 13.

The proof is similar to that of Lemma 9, where instead of using that every $2$-ary coherent configuration of order at most $8$ is separable, we apply Lemma 17 to get separability of sufficiently small configurations. Afterwards, we use the structure of configurations with thin fibers to show that the local bijections we picked are compatible with the partition in the $k$-ary interspaces. $◀$

See 2

Let $𝔄$ be a relational structure of arity $r$. Then $𝔄$ is identified by $k\text{-}\mathrm{WL}$ if and only if ${\mathrm{WL}}_k(𝔄)$ is separable. Because the $k$-ary coherent configuration ${\mathrm{WL}}_k(𝔄)$ has $c$-bounded thin fibers by Lemmas 14 and 15, Lemma 18 implies that separability of ${\mathrm{WL}}_k(𝔄)$ is equivalent to every strict algebraic automorphism of ${\mathrm{WL}}_k(𝔄)$ being induced by a combinatorial automorphism. This can be checked in the given time using Corollary 13, and in case of a negative answer, we can construct a non-isomorphic but non-distinguished structure from the strict algebraic automorphism not induced by a combinatorial one as in Theorem 1. $◀$ Note that the restriction to relational structures of arity at most $k$ is insubstantial, because the standard variant of the Weisfeiler-Leman algorithm given in Section 2 does not identify any relational structure of arity larger than $k$, simply because it does not consider tuples of length larger than $k$ and thus cannot even detect whether a relation of arity larger than $k$ is empty. While there are variants of $k$-$\mathrm{WL}$ which identify some $(k+1)$-ary relational structures, these variants can be treated similarly to decide identification by those algorithms.

We again turn to the $k$-$\mathrm{WL}$-identification problem for a fixed dimension $k\ge 2$, and show that both over uncolored simple graphs and over simple graphs with $4$-bounded abelian color classes, the problem is P-hard under logspace-uniform AC₀-reductions. We reduce from the P-hard monotone circuit value problem MCVP [17]. Our construction of a graph from a monotone circuit closely resembles the reductions of Grohe [19] to show P-hardness of the $k$-$\mathrm{WL}$-equivalence problem. A similar reduction was also used to prove P-hardness of the identification problem for the color refinement algorithm ($1$-$\mathrm{WL}$) [2].

The reduction is based on so-called one-way switches, which were introduced by Grohe [19]. These graph gadgets allow color information computed by the Weisfeiler-Leman algorithm to pass in one direction, but block it from passing in the other. And while Grohe provides one-way switches for every dimension of the Weisfeiler-Leman algorithm, his gadgets have large color classes and are difficult to analyze. Instead, we give a new construction of such gadgets with $4$-bounded color classes. We then use these one-way switches to construct a graph from an instance of the monotone circuit value problem from the identification of which we can read off the answer to the initial MCVP-query.

Fix a dimension $k\ge 2$ of the Weisfeiler-Leman algorithm. A $k$-one-way switch is a graph gadget with a pair of input vertices $\{y_1,y_2\}$ and a pair of output vertices $\{x_1,x_2\}$, which each form a color class of size $2$. A pair of vertices is split if the two vertices are colored differently and $k$-$\mathrm{WL}$ splits a pair if the coloring computed by $k$-$\mathrm{WL}$ splits the pair. The crucial property of a $k$-one-way switch is the following: if the input pair $\{y_1,y_2\}$ of the one-way switch is split, then $k$-$\mathrm{WL}$ also splits the output pair, but not the other way around. One-way switches thus only allow one-way flow of $k$-$\mathrm{WL}$-color information. In contrast to Grohe’s gadgets, our one-way switches are based on the CFI-construction [11]. We give only a brief sketch of the properties of our one-way switches here, and postpone their precise construction and properties to Appendix A.

We reduce the monotone circuit value problem to the $k$-$\mathrm{WL}$-identification problem. A monotone circuit $M$ is a circuit consisting of input nodes with values True or False, inner nodes, which are either $\mathrm{AND}$- or $\mathrm{OR}$-nodes with two inputs each, and a distinguished output node. We write $V(M)$ for the set of nodes of $M$. With a monotone circuit $M$, we associate the evaluation function ${\mathrm{val}}_M:V(M)\to \{\text{True},\text{False}\}$, which is defined in the expected way. The monotone circuit value problem asks whether the output node of a given monotone circuit evaluates to True and is P-hard by [17].

Let $M$ be a monotone circuit. We construct a colored graph $G_M$ such that for every node $a\in V(M)$, there is a vertex pair $\{a_1,a_2\}$ in $G_M$ that will be split by $k\text{-}\mathrm{WL}$ if and only if ${\mathrm{val}}_M(a)=\text{False}$. Up to the construction of the one-way switches, the construction of $G_M$ is similar to constructions employed in [19] and [2]. We use two graphs $G_{\mathrm{OR}}$ and $G_{\mathrm{AND}}$ (see Figure 3) as gadgets to simulate logic gates. These gadgets both have two input pairs and one output pair such that exchanging the two output vertices by an automorphism requires the two vertices of one (for $G_{\mathrm{OR}}$) or both (for $G_{\mathrm{AND}}$) input pairs to also be exchanged.

The formal construction of $G_M$ is depicted in Figure 4. For every node $a$ of $M$, we add a pair of vertices $\{a_1,a_2\}$ forming a color class of $G_M$. To encode the input values of the circuit, we split every pair $\{a_1,a_2\}$ corresponding to an input node $a$ of value False. For every $\mathrm{AND}$-node $a\in V(M)$ with input nodes $b$ and $b^{\prime }$, we add a freshly colored copy of the gadget $G_{\mathrm{AND}}$ from Figure 3 and identify its output pair with the pair $\{a_1,a_2\}$. Next, we connect its two input pairs via freshly colored one-way switches $O_{ba}^k$ and $O_{b^{\prime }a}^k$ to the pairs $\{b_1,b_2\}$ and $\{b_1^{\prime },b_2^{\prime }\}$ respectively. More precisely, we identify the input pairs of these one-way switches with $\{b_1,b_2\}$ or $\{b_1^{\prime },b_2^{\prime }\}$ respectively and identify their output pair with the respective input pair of the copy is identif of $G_{\mathrm{AND}}$. Analogously, we add a copy of $G_{\mathrm{OR}}$ for every $\mathrm{OR}$-node $a\in V(M)$ and connect it to its input via one-way switches as before.

This concludes the translation of the circuit itself, but for our reduction to the identification problem we need one more step: we connect all input pairs $\{a_1,a_2\}$ with ${\mathrm{val}}_M(a)=\text{True}$ to the output pair $\{c_1,c_2\}$ via additional one-way switches $O_{ca}^k$, whose input pair we identify with $\{c_1,c_2\}$ and whose output pair we identify with $\{a_1,a_2\}$. Let $G_M$ be the resulting graph. Because we color different gadgets using distinct colors, and every gadget has $4$-bounded color classes, the resulting graph $G_M$ also has $4$-bounded color classes and indeed, these color classes could also be made abelian by introducing colored edges within the gadgets. The following lemma is proven similar to [19, Section 5.4] and [2, Theorem 7.11] by using the properties of the one-way switches to bound the distinguishing power of $k$-$\mathrm{WL}$ on $G_M$ in terms of its distinguishing power on the individual gadgets.

Recall that $G_M$ contains, for every node $a$ of $M$, a vertex pair $\{a_1,a_2\}$. The essential property of the encoding of monotone circuits as graphs is the following:

Consider now the modified graph $G_M^{\ast }$ that we get by adding another freshly colored one-way switch $O_{\ast }^k$ whose input pair is $\{c_1,c_2\}$, i.e., the vertex pair corresponding to the output node of the circuit $M$. Furthermore, we split the output pair of $O_{\ast }^k$. Note that when splitting the output pair, we can choose which of the two vertices to give a fresh color to. We show that these two choices lead to non-isomorphic graphs which are distinguished by $k$-$\mathrm{WL}$ if and only if the circuit evaluates to False.

If ${\mathrm{val}}_M(c)=\text{False}$, then all input and output pairs in $G_M^{\ast }$ are split. Because all gadgets in $G_M^{\ast }$ are identified when their input and output pairs are split, and different gadgets only interact at these split pairs, the whole graph $G_M^{\ast }$ is identified.

Conversely, assume ${\mathrm{val}}_M(c)=\text{True}$, and let ${(G_M^{\ast })}^{\prime }$ be the graph constructed just like $G_M^{\ast }$, but with the colors of the two output vertices of the one-way switch $O_{\ast }^k$ exchanged. Because the pair $\{c_1,c_2\}$ is not split in $G_M$, $k\text{-}\mathrm{WL}$ cannot distinguish the two output vertices of $O_{\ast }^k$, which means that it cannot distinguish the non-isomorphic graphs $G_M^{\ast }$ and ${(G_M^{\ast })}^{\prime }$. $◀$

See 4