RWTH Aachen<EMAIL_ADDRESS>aachen.dehttps://orcid.org/0000-0001-5437-8074The research of this author has
received further funding by the European Union (ERC, SymSim, 101054974). TU
<EMAIL_ADDRESS>darmstadt.dehttps://orcid.org/0000-0003-1685-410X TU
<EMAIL_ADDRESS>darmstadt.dehttps://orcid.org/0009-0001-3585-8213 Moritz Lichter, Simon
Raßmann and Pascal Schweitzer [500]Mathematics of computing Graph algorithms
[500]Mathematics of computing Approximation algorithms [500]Theory of
computation Problems, reductions and completeness [300]Theory of computation
Complexity theory and logic The research leading to these results has received
funding from the European Research Council (ERC) under the European Union’s
Horizon 2020 research and innovation programme (EngageS: grant agreement No.
820148).

# Computational complexity of the Weisfeiler-Leman dimension

Moritz Lichter  Simon Raßmann  Pascal Schweitzer

###### Abstract

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. The dimension is a standard measure of the
descriptive complexity of a graph and recently finds various applications in
particular in the context of machine learning. In this paper, we study the
computational complexity of computing the Weisfeiler-Leman dimension. We
observe that in general the problem of deciding whether the Weisfeiler-Leman
dimension of $G$ is at most $k$ is NP-hard. This is also true for the more
restricted problem with graphs of color multiplicity at most 4. Therefore, we
study parameterized and approximate versions of the problem. We give, for each
fixed $k\geq 2$, a polynomial-time algorithm that decides whether the
Weisfeiler-Leman dimension of a given graph of color multiplicity at most $5$
is at most $k$. Moreover, we show that for these color multiplicities this is
optimal in the sense that this problem is P-hard under logspace-uniform
AC0-reductions. Furthermore, for each larger bound $c$ on the color
multiplicity and each fixed $k\geq 2$, we provide a polynomial-time
approximation algorithm for the abelian case: given a relational structure
with abelian color classes of size at most $c$, the algorithm outputs either
that its Weisfeiler-Leman dimension is at most $(k+1)c$ or that it is larger
than $k$.

###### keywords:

Weisfeiler-Leman algorithm, dimension, complexity, coherent configurations

##  1 Introduction

The _Weisfeiler-Leman algorithm_ is a simple combinatorial procedure studied
in the context of the graph isomorphism problem. For every $k\geq 1$, the
algorithm has a $k$-dimensional variant, $k$-$\mathrm{WL}$ for short, that
colors $k$-tuples of vertices according to how they structurally sit inside
the whole graph: if two tuples get different colors, they cannot be mapped
onto each other by an automorphism of the graph (while the converse is not
always true). The $1$-dimensional algorithm, which is also known as _color
refinement_ , starts by coloring each vertex according to its degree, and then
repeatedly refines this coloring by including into each vertex color the
multisets of colors of its neighbors. The $k$-dimensional variant generalizes
this idea and colors $k$-tuples of vertices instead of single vertices [41,
11].

The Weisfeiler-Leman algorithm plays an important role in both theoretic and
practical approaches to the graph isomorphism problem, but is also related to
a plethora of seemingly unrelated areas: to finite model theory and
descriptive complexity via the correspondence of $k$-$\mathrm{WL}$ to
$(k+1)$-variable first-order logic with counting [11, 26], to machine learning
via a correspondence to the expressive power of (higher-dimensional) graph
neural networks [34], to the Sherali-Adams hierarchy in combinatorial
optimization [3, 24], and to homomorphism counts from treewidth-$k$ graphs
[14].

On the side of practical graph isomorphism, the color refinement procedure is
a basic building block of the so-called _individualization-refinement
framework_ , which is the basis of almost every modern practical solver for
the graph isomorphism problem [33, 27, 28, 1]. On the side of theoretical
graph isomorphism, Babai’s quasipolynomial-time algorithm for the graph
isomorphism problem [4] uses a combination of group-theoretic techniques and a
logarithmic-dimensional Weisfeiler-Leman algorithm.

The Weisfeiler-Leman algorithm is a powerful algorithm for distinguishing non-
isomorphic graphs on its own. For every $k$, $k$-$\mathrm{WL}$ can be used as
an incomplete polynomial-time isomorphism test: if the multiset of colors of
$k$-tuples of two graphs $G$ and $H$ differ, then $G$ and $H$ cannot be
isomorphic. In this case, $k$-$\mathrm{WL}$ distinguishes $G$ and $H$,
otherwise $G$ and $H$ are $k$-$\mathrm{WL}$-equivalent. For a given graph $G$,
we say that the $k$-dimensional Weisfeiler-Leman algorithm $k$-$\mathrm{WL}$
_identifies_ $G$ if it distinguishes $G$ from every non-isomorphic graph. The
smallest such $k$ is known as the _Weisfeiler-Leman dimension of $G$_ [20].

It is known that almost all graphs have Weisfeiler-Leman dimension $1$ [5].
However, color refinement fails spectacularly on regular graphs, where it
always returns the monochromatic coloring. For these, it is known that
$2$-$\mathrm{WL}$ identifies almost all regular graphs [10, 32]. In contrast
to these positive results, for every $k$ there is some graph $G$ (even of
order linear in $k$, of maximum degree $3$, and of color multiplicity $4$,
i.e., such that no more than $4$ vertices can share the same vertex-color)
that is not identified by $k$-$\mathrm{WL}$ [11]. These so-called CFI-graphs
have high Weisfeiler-Leman dimension and are thus hard instances for
combinatorial approaches to the graph isomorphism problem.

The situation changes for restricted classes of graphs. If the Weisfeiler-
Leman dimension over some class of graphs is bounded by $k$, then the
$k$-dimensional Weisfeiler-Leman algorithm correctly decides isomorphism over
this class. And since $k$-$\mathrm{WL}$ can be implemented in polynomial time
$O(n^{k+1}\log n)$ [26], this puts graph isomorphism over such classes into
polynomial time. Examples of graph classes with bounded Weisfeiler-Leman
dimension include graphs of bounded tree-width [22], graphs of bounded rank-
width [23], graphs of color multiplicity $3$ [26], planar graphs [29], and
more generally every non-trivial minor-closed graph class [20].

In this paper, we study the computational complexity of computing the
Weisfeiler-Leman dimension. We call the problem of deciding whether the
Weisfeiler-Leman dimension of a given graph is at most $k$ the _$k$
-$\mathrm{WL}$-identification problem_. For upper complexity bounds, non-
identification of a graph $G$ can be witnessed by providing a graph $H$ that
is not distinguished from $G$ by $k$-$\mathrm{WL}$ but is also not isomorphic
to $G$. As the latter can be checked in co-NP, this places the identification
problem into the class $\Pi_{2}^{\textsf{P}}$ of the polynomial hierarchy. If
the graph isomorphism problem is solvable in polynomial time, this complexity
bound collapses to co-NP. However, there is no apparent reason why the
identification problem should not be polynomial-time decidable.

On the side of lower complexity bounds, the $1$-$\mathrm{WL}$-identification
problem is complete for polynomial time under uniform reductions in the
circuit complexity class AC0 [30, 2]. Hardness of the
$1$-$\mathrm{WL}$-identification problem does, however, not easily imply any
hardness results for the $k$-$\mathrm{WL}$-identification problem for higher
values of $k$. Indeed, no hardness results are known for $k\geq 2$. The
$2$-$\mathrm{WL}$-identification problem in particular includes the problem of
deciding whether a given strongly regular graph is determined by its
parameters, which is a baffling problem from classic combinatorics far beyond
our current knowledge. To understand the difficulties of the
$k$-$\mathrm{WL}$-identification problem better, we can again consider classes
of graphs. On every class of graphs of bounded color multiplicity, graph
isomorphism is solvable in polynomial time [6, 17], which puts the
identification problem over this class into co-NP for every $k\geq 2$. Graphs
of color multiplicity at most $3$ are identified by $2$-$\mathrm{WL}$ [26],
which makes their identification problem trivial. As shown by the CFI-graphs
[11], this is no longer true for color multiplicity $4$. Nevertheless, as
shown by Fuhlbrück, Köbler, and Verbitsky, identification of graphs of color
multiplicity at most $5$ by $2$-$\mathrm{WL}$ is polynomial-time decidable
[16]. For higher dimensions or color multiplicities essentially nothing is
known.

##### Contribution.

We extend the results of [16] for $2$-$\mathrm{WL}$ and give a polynomial-time
algorithm deciding whether a given graph of color multiplicity at most $5$ is
identified by $k\text{-}\mathrm{WL}$:

######  Theorem 1.1 (name=,restate=WLkIDccsFive).

For every $k$, there is an algorithm that decides the
$k$-$\mathrm{WL}$-identification problem for vertex- and edge-colored,
directed graphs of color multiplicity at most $5$ in time $O_{k}(n^{O(k)})$.
If such a graph $G$ is not identified by $k\text{-}\mathrm{WL}$, the algorithm
provides a witness for this, i.e., a graph $H$ that is not isomorphic to $G$
and not distinguished from $G$ by $k$-$\mathrm{WL}$.

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:

######  Theorem 1.2 (name=,restate=WLdimNPhard).

The problem of deciding, given a graph $G$ and a natural number $k$, whether
the Weisfeiler-Leman dimension of $G$ is at most $k$ is NP-hard, both over
uncolored simple graphs, and over simple graphs of color multiplicity at most
$4$.

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:

######  Theorem 1.3 (name=,restate=IdentificationPHard).

For every $k\geq 1$, the $k$-$\mathrm{WL}$-identification problem is P-hard
under uniform AC0-reductions over both uncolored simple graphs, and simple
graphs of color multiplicity $4$.

Towards generalizing Theorem 1.1 to arbitrary relational structures and larger
bounds on the color multiplicity, 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 [42] and include both CFI-graphs
[11] and multipedes [36, 35] over ordered base graphs. For such structures, we
obtain an approximation result for the Weisfeiler-Leman dimension:

######  Theorem 1.4 (name=,restate=ApproximationAbelianCC).

For all $k\geq r\geq 2$ and $c\in\mathbb{N}$, there exists an algorithm that,
for every $r$-ary relational structure $\mathfrak{A}$ of order $n$ with
abelian color classes of size at most $c$, runs in time $O_{k,c}(n^{O(k)})$,
and either

  1. 1.

outputs a structure $\mathfrak{B}$ not isomorphic to $\mathfrak{A}$ and not
distinguished from $\mathfrak{A}$ by $k$-$\mathrm{WL}$, or

  2. 2.

correctly returns that the Weisfeiler-Leman dimension of $\mathfrak{A}$ is at
most $(k+1)c$.

Similar approximation algorithms exist e.g. for tree-width [38, 31] and rank-
width [37].

##### Techniques.

To prove Theorem 1.1, we exploit the close connection between the coloring
computed by $k$-$\mathrm{WL}$ and $k$-ary coherent configurations. These
structures come with two notions of isomorphisms, algebraic ones and
combinatorial ones. Similarly to [16], 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 that of $k$-ary coherent configurations where no interspace
contains a disjoint union of stars. 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 of bounded color multiplicity, which is polynomial-time
solvable [6, 17].

NP-hardness in Theorem 1.2 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 1.3, we adapt a construction by Grohe [19] to encode 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
$k$-$\mathrm{WL}$-identification problem. The main difficulty was showing
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 [11]. This construction simplifies proofs and more
importantly yields graphs of color multiplicity $4$ for every $k$. This shows
hardness for the $k$-$\mathrm{WL}$-equivalence and
$k$-$\mathrm{WL}$-identification problems even for graphs of color
multiplicity $4$.

The main obstacle to generalize Theorem 1.1 to higher bounds on the color
multiplicity is that there are $k$-$\mathrm{WL}$-equivalent graphs that yield
non-isomorphic star-free $k$-ary coherent configurations. To make up for this,
we restrict ourselves to $k$-$\mathrm{WL}$-equivalent structures that are at
least locally isomorphic. This restriction comes at the cost of only providing
an approximation algorithm in Theorem 1.4. However, to be able to apply the
techniques used to prove Theorem 1.1, we also have to restrict to structures
with abelian color classes, which ensures that algebraic isomorphisms have a
group-like structure.

##  2 The Weifeiler-Leman algorithm and coherent configurations

#### Preliminaries.

For $n\in\mathbb{N}$, we set $[n]\coloneqq\\{1,\dots,n\\}$. For a set $A$, the
set of all $k$-element subsets of $A$ is denoted by $\binom{A}{k}$. A simple
graph is a pair $G=(V(G),E(G))$ of a set $V(G)$ of _vertices_ and a set
$E(G)\subseteq\binom{V(G)}{2}$ of undirected edges. For a directed graph, we
allow $E(G)\subseteq V(G)^{2}\setminus\\{(v,v)\colon 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\colon V(G)\to C$ for some finite, ordered set $C$ of colors. Similarly,
an _edge-coloring_ is a map $\eta\colon E(G)\to C$. A (vertex-)color class is
a set $\chi^{-1}(c)$ for some vertex color $c\in C$. The _color multiplicity_
of a vertex-colored graph $(G,\chi)$ is the maximal order of a color class.

Relational structures are a higher-arity analogue of graphs. Formally, a _$k$
-ary relational structure_ $\mathfrak{A}$ is a tuple
$(V(\mathfrak{A}),R_{1},\dots,R_{\ell})$ of vertices $V(\mathfrak{A})$ and
relations $R_{i}\subseteq V(\mathfrak{A})^{r_{i}}$ with $r_{i}\leq 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 the _color
multiplicity_ of a vertex-colored relational structure $\mathfrak{A}$ to be
the maximal order of a color class.

An _isomorphism_ between graphs $G$ and $H$ is a bijection $\varphi\colon
V(G)\to V(H)$ such that $uv\in E(G)$ if and only if $\varphi(u)\varphi(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.

#### The Weisfeiler-Leman algorithm.

For every $k\geq 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.,
${\mathbf{x}}=(x_{1},\dots,x_{k}),{\mathbf{y}}=(y_{1},\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},\dots,x_{k}\\}]$ and $G[\\{y_{1},\dots,y_{k}\\}]$. In each
iteration, this coloring is refined as follows: if $\chi^{G}_{i}\colon
V(G)^{k}\to C_{i}$ is the coloring obtained after $i$ refinement rounds, the
coloring $\chi^{G}_{i+1}\colon V(G)^{k}\to C_{i+1}$ is defined as
$\chi^{G}_{i+1}({\mathbf{x}})\coloneqq(\chi^{G}_{i}({\mathbf{x}}),M_{\mathbf{x}}^{i})$,
where

$M_{\mathbf{x}}^{i}=\left\\{\\!\\!\left\\{\Bigl{(}\chi^{G}_{i}\bigl{(}{\mathbf{x}}\frac{y}{1}\bigr{)},\dots,\chi^{G}_{i}\bigl{(}{\mathbf{x}}\frac{y}{k}\bigr{)}\Bigr{)}\colon
y\in V(G)\right\\}\\!\\!\right\\}$

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

We say that $k$-$\mathrm{WL}$ _distinguishes two $k$-tuples
${\mathbf{x}},{\mathbf{y}}\in V(G)^{k}$_ if
$\chi^{G}_{\infty}({\mathbf{x}})\neq\chi^{G}_{\infty}({\mathbf{y}})$ and that
$k$-$\mathrm{WL}$ _distinguishes two $\ell$-tuples
${\mathbf{x}},{\mathbf{y}}\in V(G)^{\ell}$_ for $\ell<k$ if $k$-$\mathrm{WL}$
distinguishes the two $k$-tuples we get by repeating the last entries of
${\mathbf{x}}$ respectively ${\mathbf{y}}$. Finally, _$k$ -$\mathrm{WL}$
distinguishes two graphs_ $G$ and $H$ if there is a color $c$ such that

$\left|\left\\{{\mathbf{x}}\in
V(G):\chi_{\infty}^{G}({\mathbf{x}})=c\right\\}\right|\neq\left|\left\\{{\mathbf{x}}\in
V(H)\colon\chi_{\infty}^{H}({\mathbf{x}})=c\right\\}\right|.$

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 $\operatorname{WL-
dim}(G)$.

If $c_{1},\dots,c_{k}$ are colors assigned by the stable coloring $\chi_{i}$,
then the multiplicity of the tuple $(c_{1},\dots,c_{k})$ in the multiset
$M^{i}_{{\mathbf{x}}}$ is given by

$p^{\mathbf{x}}_{c_{1},\dots,c_{k}}\coloneqq\left|\left\\{y\in
V(G)\colon\chi_{i}\left({\mathbf{x}}\frac{y}{i}\right)=c_{i}\text{ for all
}i\in[k]\right\\}\right|.$

These numbers, which are called _intersection numbers_ , fully determine the
multiset $M^{i}_{{\mathbf{x}}}$. In the theoretical study of the Weisfeiler-
Leman algorithm, these numbers are often quite handy to work with compared to
the multiset view from the definition. For example, the statement that a
coloring $\chi$ is stable under $k$-$\mathrm{WL}$-refinement can be expressed
as the intersection numbers $p^{{\mathbf{x}}}_{c_{1},\dots,c_{k}}$ being
determined by $\chi({\mathbf{x}})$ and not depending on ${\mathbf{x}}$ itself.
This leads to the notion of _coherent configurations_.

As every coloring of $k$-tuples also induces a coloring of $\ell$-tuples for
$\ell\leq k$ by repeating the last entry, $k$-$\mathrm{WL}$ is at least as
powerful in distinguishing graphs as $\ell$-$\mathrm{WL}$ and this hierarchy
is actually strict [11]. Completely analogously, $k$-$\mathrm{WL}$ can be
applied to relational structures.

#### Coherent configurations.

For an introduction to ($2$-ary) coherent configurations we refer to [12] and
for their connection to the Weisfeiler-Leman algorithm we refer to [16]. For
$k\geq 2$, a _$k$ -ary rainbow_ is a pair $(V,\mathcal{R})$ of a finite set of
vertices $V$ and a partition $\mathcal{R}$ of $V^{k}$, whose elements are
called _basis relations_ , that satisfies the following two conditions:

(R1)

For every basis relations $R\in\mathcal{R}$, all tuples
${\mathbf{x}},{\mathbf{y}}\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)

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

Because the vertex set $V$ is determined by the partition $\mathcal{R}$, we
also write $\mathcal{R}$ to denote the rainbow $(V,\mathcal{R})$ and in this
case write $V(\mathcal{R})$ for its vertex set $V$.

A _$k$ -ary coherent configuration_ is a $k$-ary rainbow $\mathcal{C}$ that is
stable under $k$-$\mathrm{WL}$-refinement. More formally, this means that

(C)

for all basis relations $R,R_{1},\dots,R_{k}\in\mathcal{C}$, the _intersection
number_

$p\left(R;R_{1},\dots,R_{k}\right)\coloneqq\left|\left\\{y\in
V(\mathcal{C})\colon{\mathbf{x}}\frac{y}{i}\in R_{i}\text{ for all
}i\in[k]\right\\}\right|$

is the same for all choices of ${\mathbf{x}}\in R$ and is thus well-defined.

For $\ell\leq k$, the partition of $k$-vertex tuples of an $\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.

##### Induced configurations.

If $\mathcal{R}$ is an $\ell$-ary rainbow for $\ell\leq k$, we can interpret
$\mathcal{R}$ as the $k$-ary rainbow $\mathcal{R}|^{k}$ by partitioning
$k$-tuples according to the basis relations of the $\ell$-subtuples they
contain. Formally, let $\sim_{\mathcal{R}}$ be the equivalence relation on
$V(\mathcal{R})^{\ell}$ whose equivalence classes are the basis relations of
$\mathcal{R}$. We define the equivalence relation $\sim_{\mathcal{R}}^{k}$ on
$V(\mathcal{R})^{k}$ by writing ${\mathbf{x}}\sim_{k}{\mathbf{y}}$ if and only
if for all $I\in\binom{[k]}{\ell}$ we have
${\mathbf{x}}|_{I}\sim_{\mathcal{R}}{\mathbf{y}}|_{I}$, where
${\mathbf{x}}|_{I}$ is the subtuple of ${\mathbf{x}}$ for which all indices
not in $I$ are deleted. The basis relations of $\mathcal{R}|^{k}$ are the
equivalence classes of $\sim_{\mathcal{R}}^{k}$.

For every $k$-ary rainbow $\mathcal{R}$, there is a unique coarsest $k$-ary
coherent configuration $\operatorname{WL}_{k}(\mathcal{R})$ that is at least
as fine as $\mathcal{R}$ and is called the _$k$ -ary coherent closure_ of
$\mathcal{R}$. For an $\ell\leq k$ and an $\ell$-ary rainbow $\mathcal{R}$, we
also write $\operatorname{WL}_{k}(\mathcal{R})$ for
$\operatorname{WL}_{k}(\mathcal{R}|^{k})$. Similarly, for an $\ell$-ary
relational structure $\mathfrak{A}$, we write
$\operatorname{WL}_{k}(\mathfrak{A})$ for the partition of
$V(\mathfrak{A})^{k}$ into $k\text{-}\mathrm{WL}$-color classes.

Every $k$-ary coherent configuration $\mathcal{C}$ induces the $\ell$-ary
coherent configuration $\mathcal{C}|_{\ell}$ for every $\ell\leq k$ by
considering the partition of tuples of the form
$(x_{1},\dots,x_{\ell},\dots,x_{\ell})\in V(\mathcal{C})^{k}$. This $\ell$-ary
coherent configuration is called the _$\ell$ -skeleton of $\mathcal{C}$_. For
every basis relation $R\in\mathcal{C}$ and every subset
$I\in\binom{[k]}{\ell}$ of the indices, the set
$R_{I}\coloneqq\\{{\mathbf{x}}|_{I}\colon{\mathbf{x}}\in R\\}$ is a basis
relation of $\mathcal{C}|_{\ell}$ and called the _$I$ -face_ of $R$. For basis
relations $R\in\mathcal{C}|_{\ell}$ and $T\in\mathcal{C}$, we get well-defined
_extension numbers_ $p\left(R;T\right)\coloneqq|\\{{\mathbf{y}}\in
V(\mathcal{C})^{k-\ell}\colon{\mathbf{xy}}\in T\\}|$ for some (and every)
${\mathbf{x}}\in R$.

For $\ell=1$, the $1$-skeleton yields a partition of $V(\mathcal{C})$, whose
partition classes are called _fibers_. We denote the set of fibers by
$F(\mathcal{C})$. The color multiplicity of $\mathcal{C}$ is the maximal order
of a fiber of $\mathcal{C}$. Between two fibers $X$ and $Y$, the induced
configuration $\mathcal{C}|_{2}$ further induces a partition
$\mathcal{C}|_{2}[X,Y]$ of $X\times Y$, called an _interspace_.

We call a $k$-ary coherent configuration $\mathcal{C}$ _$\ell$ -induced_ if it
is the coherent closure of its $\ell$-skeleton, i.e., if
$\mathcal{C}=\operatorname{WL}_{k}(\mathcal{C}|_{\ell})$. This is equivalent
to $\mathcal{C}$ being the coherent closure of some $\ell$-ary rainbow. In
particular, the $k$-ary coherent closure of a (directed, colored) graph is
$2$-induced and, more generally, the $k$-ary coherent closure of an $\ell$-ary
relational structure is $\ell$-induced for every $k\geq\ell$.

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

##### Algebraic and combinatorial isomorphisms.

There are two notions of isomorphism for two $k$-ary coherent configurations
$\mathcal{C}$ and $\mathcal{D}$. First, a _combinatorial isomorphism_ is a
bijection $\varphi\colon V(\mathcal{C})\to V(\mathcal{D})$ that preserves the
partition into basis relations, i.e., for every basis relation
$R\in\mathcal{C}$, the mapped set
$R^{\varphi}\coloneqq\\{(\varphi(x_{1}),\dots,\varphi(x_{k}))\colon(x_{1},\dots,x_{k})\in
R\\}$ is a basis relation of $\mathcal{D}$. Combinatorial isomorphisms are
thus isomorphisms between certain colored variants of $\mathcal{C}$ and
$\mathcal{D}$ and the notion also applies to rainbows.

Second, an _algebraic isomorphism_ is a map $f\colon\mathcal{C}\to\mathcal{D}$
between the two partitions that preserves the intersection numbers. More
formally, we require that

(A1)

for all $R\in\mathcal{C}$, the relations $R$ and $f(R)$ have the same equality
type,

(A2)

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

(A3)

for all $R,T_{1},\dots,T_{k}\in\mathcal{C}$, we have
$p\left(R;T_{1},\dots,T_{k}\right)=p\left(f(R);f(T_{1}),\dots,f(T_{k})\right)$,

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. If
$f\colon\mathcal{C}\to\mathcal{D}$ is an algebraic isomorphism, then $f$
induces an algebraic isomorphism
$f|_{\ell}\colon\mathcal{C}|_{\ell}\to\mathcal{D}|_{\ell}$ for every $\ell\leq
k$. A combinatorial (respectively algebraic) _automorphism of $\mathcal{C}$_
is a combinatorial (respectively algebraic) isomorphism from $\mathcal{C}$ 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
[16, Lemma 2.4]):

######  Lemma 2.1.

Let $\mathcal{R}$ be a $k$-ary rainbow,
$\mathcal{C}=\operatorname{WL}_{k}(\mathcal{R})$, and
$f\colon\mathcal{C}\to\mathcal{D}$ an algebraic isomorphism. Then

  1. 1.

$\mathcal{D}=\operatorname{WL}_{k}(\mathcal{R}^{f})$, in particular, if
$\mathcal{C}$ is $2$-induced, then so is $\mathcal{D}$,

  2. 2.

$f$ is fully determined by its action on basis relations in $\mathcal{R}$, and

  3. 3.

if $f|_{\mathcal{R}}$ is induced by a combinatorial isomorphism $\varphi$,
then $\varphi$ induces $f$.

A $k$-ary coherent configuration $\mathcal{C}$ is called _separable_ if every
algebraic isomorphism $f\colon\mathcal{C}\to\mathcal{D}$ from $\mathcal{C}$ 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 [16,
Theorem 2.5]):

######  Lemma 2.2.

Let $\ell\leq k$ and $\mathfrak{A}$ be an $\ell$-ary relational structure.
Then $\mathfrak{A}$ is identified by the $k$-dimensional Weisfeiler-Leman
algorithm if and only if $\operatorname{WL}_{k}(\mathfrak{A})$ is separable.

#### The bijective pebble game.

The question whether $k$-$\mathrm{WL}$ can distinguish two graphs $G$ and $H$
has another characterization in terms of the so-called _bijective
$(k+1)$-pebble game_. In this game, there are two players: Spoiler and
Duplicator. Game positions are partial maps ${\mathbf{g}}\mapsto{\mathbf{h}}$
between $G$ and $H$, where both tuples contain at most $k+1$ elements. We also
sometimes identify such partial maps with the set $P=\\{g_{i}\mapsto
h_{i}\colon i\leq|{\mathbf{g}}|\\}$. We think of these maps as $k+1$ pairs of
corresponding pebbles placed in the two graphs.

If such a partial map is not a partial isomorphism, i.e., not an isomorphisms
on the induced subgraphs, Spoiler wins immediately. Otherwise, at the
beginning of each turn, Spoiler picks up one pebble pair, either from the
board if all $k+1$ pairs are placed, or from the side if there are pebble
pairs left. Duplicator responds by giving a bijection $\varphi\colon V(G)\to
V(H)$ between the two graphs. Spoiler then places the pebble pair they picked
up on a pair $(g,\varphi(g))$ of vertices of their choice. The game then
continues in the resulting new position.

We say that Spoiler wins if the graphs have differing cardinality or they can
reach a position that is no longer a partial isomorphism (and thus win
immediately). Duplicator wins the game if they can find responses to Spoiler’s
moves indefinitely.

######  Lemma 2.3 ([25]).

Let $G$ and $H$ be two graphs, and ${\mathbf{g}}\in V(G)^{k}$ and
${\mathbf{h}}\in V(H)^{k}$ two tuples of vertices. Then the following are
equivalent:

  1. (i)

Duplicator has a winning strategy in position
${\mathbf{g}}\mapsto{\mathbf{h}}$ of the bijective $(k+1)$-pebble game between
$G$ and $H$,

  2. (ii)

The stable colors computed by $k$-$\mathrm{WL}$ for the tuples ${\mathbf{g}}$
and ${\mathbf{h}}$ agree.

#### The CFI-construction.

CFI-graphs are certain graphs with high Weisfeiler-Leman dimension [11]. To
construct them, we start with a base graph $G$, which is a connected simple
graph, and a function $f\colon E(G)\to\mathbb{F}_{2}$. For a vertex $v\in
V(G)$, we denote the set of edges incident to $v$ by $E[v]\coloneqq\\{uv\colon
v\in N_{G}(v)\\}\subseteq E(G)$. Now, to construct the CFI-graph
$\operatorname{CFI}(G,f)$, we replace each vertex $v\in V(G)$ by a gadget
$X_{v}$ which consists of inner vertices
$I_{v}\coloneqq\\{v\\}\times\\{{\mathbf{x}}\in\mathbb{F}_{2}^{E[v]}\colon\sum{\mathbf{x}}=0\\}$
and outer vertices $\\{v\\}\times\\{(e,i)\colon e\in
E[v],i\in\mathbb{F}_{2}\\}$. Inside each gadget, the inner and outer vertices
each form an independent set, and an inner vertex $(v,{\mathbf{x}})$ and outer
vertex $(v,e,i)$ are connected by an edge if and only if ${\mathbf{x}}_{e}=i$.
The resulting gadget for a vertex of degree $3$ is depicted in Figure 1.

Figure 1: A CFI-gadget for a vertex of degree $3$, consisting of four inner
vertices and three outer pairs

Next, we define the edge set between different gadgets. For every edge
$e=uv\in E(G)$, we connect the outer vertices $(u,e,i)$ and $(v,e,j)$ if and
only if $i+j=f(e)$ and add no further edges. Thus, corresponding outer vertex
pairs $(u,e,\cdot)$ and $(v,e,\cdot)$ are always connected by a matching,
which is either _untwisted_ if $f(e)=0$, or _twisted_ if $f(e)=1$.

Finally, we define a vertex coloring on this graph. For every vertex $v$, we
turn the set $I_{v}$ of inner vertices into a color class of size
$2^{d(v)-1}$. Moreover, we turn each outer pair $\\{(v,e,0),(v,e,1)\\}$ into a
color class of size $2$. This finishes the construction of CFI-graphs.

It turns out that for two functions $f,g\colon E(G)\to\mathbb{F}_{2}$, we have
$\operatorname{CFI}(G,f)\cong\operatorname{CFI}(G,g)$ if and only if $\sum
f=\sum g$, meaning that every even number of twists cancels out. Thus, we also
write $\operatorname{CFI}(G,0)$ and $\operatorname{CFI}(G,1)$ for the
_untwisted_ and _twisted_ CFI-graphs over the base graph $G$.

To understand the power of the Weisfeiler-Leman algorithm on CFI-graphs, it is
convenient to study _tree-width_ , which is a graph parameter that intuitively
measures how far a graph is from being a tree. In this work, we do not need
the formal definition of tree-width, and refer to [8]. The power of the
Weisfeiler-Leman algorithm to distinguish CFI-graphs can now conveniently be
expressed in terms of the tree-width of the base graphs, see [21].

######  Lemma 2.4.

For every base graph $G$ of tree-width $\operatorname{tw}(G)\geq 2$, we have

$\operatorname{WL-dim}(\operatorname{CFI}(G,0))=\operatorname{WL-
dim}(\operatorname{CFI}(G,1))=\operatorname{tw}(G).$

######  Proof 2.5.

We first show that CFI-graphs can be easily distinguished from other graphs.

######  Claim 1.

For every base graph $G$, $2$-$\mathrm{WL}$ distinguishes CFI-graphs over $G$
from all other graphs.

Let $G$ be a base graph, $i\in\mathbb{F}_{2}$, and $H$ be some graph not
isomorphic to $\operatorname{CFI}(G,0)$ or $\operatorname{CFI}(G,1)$. If $H$
has a color class of different size than the one of the same color in
$\operatorname{CFI}(G,i)$, then $2$-$\mathrm{WL}$ certainly distinguishes $H$
and $\operatorname{CFI}(G,i)$. Let $u\in V(G)$ be of degree $d$. Let $c$ be
the color of inner vertices of the gadget of $u$ and $c_{1},\dots,c_{d}$ be
the colors of outer vertices of this gadget. Then every vertex of color $c$
has exactly one neighbor of each $c_{i}$ and no others. For each $i\in[d]$,
the two vertices of color $c_{i}$ have the same number of neighbors in $c$, no
common neighbor in $c$, and no neighbor in all $c_{j}$. Finally, for every two
$c$-vertices $u$ and $v$, the number of $i\in[d]$, for which $u$ and $v$ have
a different $c_{i}$-neighbor, is even. All these conditions can easily be
recognized by $2$-$\mathrm{WL}$ and hence $2$-$\mathrm{WL}$ identifies all
CFI-gadgets. If $e=uv\in E(G)$, let $c$ and $d$ be the color classes for the
outer vertices of the gadgets for $u$ respectively $v$ for the edge $e$. Then
$c$ and $d$ are of size two and connected by a matching, which is also easily
identified by $2$-$\mathrm{WL}$. Hence, $2$-$\mathrm{WL}$ distinguishes
$\operatorname{CFI}(G,i)$ from $H$.

We present another modified CFI-construction. For a base graph $G$ and a
function $f\colon E(G)\to\mathbb{F}_{2}$, let
$\operatorname{CFI}^{\prime}(G,f)$ be the graph obtained from
$\operatorname{CFI}(G,f)$ in the following way: The vertex set of
$\operatorname{CFI}^{\prime}(G,f)$ is the set of all inner vertices of all
CFI-gadgets in $\operatorname{CFI}(G,f)$. Two inner vertices
$(u,{\mathbf{x}})$ and $(v,{\mathbf{y}})$ are adjacent in
$\operatorname{CFI}^{\prime}(G,f)$ whenever $uv\in E(G)$ and
${\mathbf{x}}_{uv}+{\mathbf{y}}_{uv}=f(uv)$. This is equivalent to that there
is a path of length $3$ between $(u,{\mathbf{x}})$ and $(v,{\mathbf{y}})$
(namely the path
$(u,{\mathbf{x}}),(u,uv,{\mathbf{x}}_{uv}),(v,uv,{\mathbf{y}}_{uv}),(v,{\mathbf{y}})$).
These modified CFI-construction shares all important properties with the one
presented here, in particular,
$\operatorname{CFI}^{\prime}(G,f)\cong\operatorname{CFI}^{\prime}(G,g)$ if and
only if $\sum f=\sum g$. The following claim is well-known (see [11, 13, 21]):

######  Claim 2.

For every $k\geq 3$ and every base graph $G$, Spoiler wins the bijective
$k$-pebble game on $\operatorname{CFI}^{\prime}(G,0)$ and
$\operatorname{CFI}^{\prime}(G,1)$ if and only if Spoiler wins the bijective
$k$-pebble game on $\operatorname{CFI}(G,0)$ and $\operatorname{CFI}(G,1)$.

The main insight to prove this lemma is that it is never beneficial for
Spoiler to place a pebble on an outer vertex apart from the very end of the
game because an outer vertex $(u,e,i)$ is uniquely identified by an inner
vertex $(u,{\mathbf{x}})$ such that ${\mathbf{x}}_{e}=i$.

######  Claim 3 ([21]).

For every $k\geq 3$ and every base graph $G$, Spoiler wins the bijective
$(k+1)$-pebble game on $\operatorname{CFI}^{\prime}(G,0)$ and
$\operatorname{CFI}^{\prime}(G,1)$ if and only if $G$ has tree-width
$\operatorname{tw}(G)\leq k$.

Now finally let $G$ be a base graph of tree-width $\operatorname{tw}(G)\geq
2$. By Claims 2 and 3 and Lemma 2.3, $k$-$\mathrm{WL}$ distinguishes
$\operatorname{CFI}(G,0)$ and $\operatorname{CFI}(G,1)$ if and only if
$k\geq\operatorname{tw}(G)$. This implies $\operatorname{WL-
dim}(\operatorname{CFI}(G,i))\geq\operatorname{tw}(G)$ for both
$i\in\mathbb{F}_{2}$. By Claim 1, $2$-$\mathrm{WL}$ distinguishes CFI-graphs
over $G$ from all other graphs. Since there are only two non-isomorphic CFI-
graphs over $G$ and $\operatorname{tw}(G)$-$\mathrm{WL}$ distinguishes them,
$\operatorname{tw}(G)$-$\mathrm{WL}$ identifies CFI-graphs over $G$ and thus
$\operatorname{WL-dim}(\operatorname{CFI}(G,i))\leq\operatorname{tw}(G)$ for
both $i\in\mathbb{F}_{2}$. This implies $\operatorname{WL-
dim}(\operatorname{CFI}(G,0))=\operatorname{WL-
dim}(\operatorname{CFI}(G,1))=\operatorname{tw}(G)$.

##  3 Deciding identification for graphs of color multiplicity 5

As recently shown [16], identification of a given graph of color multiplicity
at most $5$ by $2\text{-}\mathrm{WL}$ is polynomial-time decidable. We extend
this result to arbitrary dimensions of the Weisfeiler-Leman algorithm. We
adapt the approach of [16] and solve the separability for $2$-induced $k$-ary
coherent configurations of color multiplicity $5$ instead. We generalize the
elimination of interspaces containing a matching and interspaces of type
$2K_{1,2}$ in order to reduce to _star-free_ $2$-induced $k$-ary coherent
configurations. By characterizing separability using certain automorphism
groups, we provide a new reduction of the separability problem for such
configurations to graph isomorphism of bounded color multiplicity, which can
be solved in polynomial time.

###  3.1 Disjoint unions of stars

Let $\mathcal{C}$ be a $k$-ary coherent configuration and $X,Y\in
F(\mathcal{C})$ two distinct fibers. A _disjoint union of stars_ between $X$
and $Y$ is a basis relation $S\in\mathcal{C}|_{2}[X,Y]$ such that every vertex
in $Y$ is incident to exactly one edge in $S$. If no interspace of
$\mathcal{C}$ contains a disjoint union of stars, $\mathcal{C}$ is called
_star-free_.

In this section, we want to show that whenever $\mathcal{C}|_{2}[X,Y]$
contains a disjoint union of stars, then $\mathcal{C}$ is separable if and
only if $\mathcal{C}\setminus X\coloneqq\mathcal{C}[V(\mathcal{C})\setminus
X]$ is separable. This allows us to reduce the separability problem to the
class of star-free $k$-ary coherent configurations. As we will see, this is
possible because the configuration $\mathcal{C}$ is fully determined by the
configuration $\mathcal{C}\setminus X$, together with the information how the
disjoint union of stars in $\mathcal{C}[X,Y]$ attaches to $Y$.

For a disjoint union of stars $S\in\mathcal{C}|_{2}[X,Y]$, we define a map

$\displaystyle\nu_{S}\colon V(\mathcal{C})$ $\displaystyle\to
V(\mathcal{C})\setminus Y,$ $\displaystyle v$
$\displaystyle\mapsto\begin{cases}v&\text{if }v\notin Y,\\\ w&\text{if }v\in
Y\text{ and }wv\in S.\end{cases}$

Moreover, we denote for every $I\subseteq[k]$ by $\nu_{S}^{I}\colon
V(\mathcal{C})^{k}\to V(\mathcal{C})^{k}$ the map defined via
$\nu_{S}^{I}(y_{1},\dots,y_{k})\coloneqq(z_{1},\dots,z_{k})$, where
$z_{i}\coloneqq\nu_{S}(y_{i})$ if $i\in I$ and $z_{i}\coloneqq y_{i}$ for
every $i\in[k]\setminus I$.

######  Lemma 3.1.

Let $\mathcal{C}$ be a $k$-ary coherent configuration, $X,Y\in F(\mathcal{C})$
two distinct fibers and $S\in\mathcal{C}|_{2}[X,Y]$ a disjoint union of stars
between $X$ and $Y$. For every subset $I\subseteq[k]$ and every basis relation
$R\in\mathcal{C}$, we have $\nu_{S}^{I}(R)\in\mathcal{C}$.

Moreover, for every algebraic isomorphism $f\colon\mathcal{C}\to\mathcal{D}$,
the basis relation $f(S)$ is a disjoint union of stars in $\mathcal{D}$ (with
the same degree at $f(X)$) and $f\circ\nu_{S}^{I}=\nu_{f(S)}^{I}\circ f$ for
every $I\subseteq[k]$.

######  Proof 3.2.

If $I=\\{i_{1},\dots,i_{\ell}\\}$, then we can write
$\nu_{S}^{I}=\nu_{S}^{\\{i_{1}\\}}\circ\dots\circ\nu_{S}^{\\{i_{\ell}\\}}$. As
both claims of Lemma 3.1 are compatible with compositions, it thus suffices to
consider the case that $I=\\{i\\}$ is a singleton. By symmetry, we can assume
w.l.o.g. that $i=1$.

Now, let $R$ be an arbitrary basis relation. If the $\\{1\\}$-face of $R$ is
not $Y$, then $\nu_{S}^{\\{1\\}}(R)=R$ and we are done. Otherwise, pick
${\mathbf{x}}\in R$ and let $R_{1}$ be the basis relation containing
$\nu_{S}^{\\{1\\}}({\mathbf{x}})$. Furthermore, for all $j\neq 1$ we set

$R_{j}\coloneqq\\{{\mathbf{z}}\in V(\mathcal{C})^{k}\colon z_{j}z_{1}\in
S\\}.$

Then $R_{j}$ is the union of all basis relations whose $\\{1,j\\}$-face is
$S^{-1}$. This in particular implies that the intersection number
$p\left(R;R_{1},\dots,R_{k}\right)$ is well-defined, because it can be
expressed as the sum over all intersection numbers with respect to basis
relations $T_{1},\dots,T_{k}$ contained in $R_{1},\dots,R_{k}$. Further,
$p\left(R;R_{1},\dots,R_{k}\right)\geq 1$ because
${\mathbf{x}}\frac{\nu_{S}(x_{1})}{i}\in R_{i}$ for all $i\in[k]$. Moreover,
the relations $R_{2},\dots,R_{k}$ enforce that the only element witnessing
that the intersection number is non-zero must be the unique $S$-neighbour of
$x_{1}$. This implies $p\left(R;R_{1},\dots,R_{k}\right)=1$ and furthermore
that $\nu_{S}^{\\{1\\}}({\mathbf{y}})\in R_{1}$ for all ${\mathbf{y}}\in R$.
It follows that $\nu_{S}^{\\{1\\}}(R)\subseteq R_{1}$.

To prove that this inclusion cannot be strict, we now set

$R_{j}^{\prime}\coloneqq\\{{\mathbf{z}}\in V(\mathcal{C})^{k}\colon
z_{1}z_{j}\in S\\}$

with the indices $1$ and $j$ exchanged in comparison to the relation $R_{j}$
from before. Then,

$p\left(R_{1};R,R_{2}^{\prime},\dots,R_{k}^{\prime}\right)\geq 1$

because $\nu_{S}^{\\{s\\}}({\mathbf{x}})\frac{x_{1}}{1}\in R$ and
$\nu_{S}^{\\{s\\}}({\mathbf{x}})\frac{x_{1}}{i}\in R_{i}^{\prime}$ for all
$i\in[k]\setminus\\{1\\}$. But this means that for every ${\mathbf{y}}\in
R_{1}$, there must be some $z\in V(\mathcal{C})$ with $y_{1}z\in S$ such that
${\mathbf{y}}\frac{z}{1}\in R$. But then,

${\mathbf{y}}=\nu_{S}^{\\{1\\}}\left({\mathbf{y}}\frac{z}{1}\right)\in\nu_{S}^{\\{1\\}}(R),$

which proves $\nu_{S}^{\\{1\\}}(R)=R_{1}\in\mathcal{C}$.

The fact that $f(S)$ is again a disjoint union of stars follows from the fact
that algebraic isomorphisms preserve degrees. Now, the same argument as before
shows that $\nu_{S}^{\\{1\\}}(R)$ is the unique basis relation $R_{1}$
satisfying $p\left(R;R_{1},\dots,R_{k}\right)=1$ with the relations $R_{j}$
for $j>1$ defined as before. These relations were defined only in terms of
$S$, which means that they are compatible with all algebraic isomorphisms $f$.
Thus, we have

$p\left(f(R);f(R_{1}),f(R_{2}),\dots,f(R_{k})\right)=1.$

But by the same reasoning as before, $\nu_{f(S)}^{\\{1\\}}(f(R))$ is the
unique basis relation $R_{1}^{\prime}$ satisfying

$p\left(f(R);R_{1}^{\prime},f(R_{2}),\dots,f(R_{k})\right)=1,$

meaning that

$f\left(\nu_{S}^{\\{1\\}}(R)\right)=\nu_{f(S)}^{\\{1\\}}(f(R)).$

This proves $f\circ\nu_{S}^{I}=\nu_{f(S)}^{I}\circ f$.

The above lemma in particular implies that the basis relations of
$\mathcal{C}$ are fully determined by those of $\mathcal{C}\setminus X$.
Indeed, if $R$ is a basis relation of $\mathcal{C}$ and ${\mathbf{x}}\in R$,
let $I\subseteq[k]$ be the set of $X$-components of ${\mathbf{x}}$. Then, for
every $i\in I$, we pick a $\nu_{S}$-preimage $y_{i}$ of $x_{i}$. If we now
define ${\mathbf{y}}\coloneqq{\mathbf{x}}\left(\frac{y_{i}}{i}\right)_{i\in
I}$, we get ${\mathbf{x}}=\nu_{S}^{I}({\mathbf{y}})$ and thus
$R=T^{\nu_{S}^{I}}$, where $T\in\mathcal{C}\setminus X$ is the basis relation
containing ${\mathbf{y}}$.

Together with Lemma 3.1, this implies that the basis relations of
$\mathcal{C}$ are precisely those of the form $T^{\nu_{S}^{I}}$ for
$T\in\mathcal{C}\setminus X$ and $I\subseteq[k]$. Moreover, we can assume that
$I$ is a subset of the set of $Y$-components of $T$. These representations of
basis relations of $\mathcal{C}$ are, however, not necessarily unique.

Before we are ready to eliminate all interspaces with a disjoint union of
stars, we need one more technical observation

######  Lemma 3.3.

If $S\in\mathcal{C}|_{2}[X,Y]$ is a disjoint union of stars, then the relation

$\mathsf{Eq}_{S}\coloneqq\\{vw\in Y^{2}\colon\nu_{S}(v)=\nu_{S}(w)\\}$

is a union of $2$-ary basis relations. Moreover, for every algebraic
isomorphism $f\colon\mathcal{C}\to\mathcal{D}$, we have
$f(\mathsf{Eq}_{S})=\mathsf{Eq}_{f(S)}$.

######  Proof 3.4.

It suffices to assume that $\mathcal{C}$ is a $2$-ary coherent configuration.
Then, $vw\in\mathsf{Eq}_{S}$ if and only if for some $z$ we have $zv,zw\in S$.
If $E$ is the basis relation of $\mathcal{C}$ containing $vw$, this is
equivalent to $p\left(E;S,S^{-1}\right)\geq 1$, where $S^{-1}=\\{yx\colon
xy\in S\\}$. Because this property depends only on the basis relation
containing $vw$ and not on $vw$ itself, the first claim follows.

For the second claim, note that $R\subseteq\mathsf{Eq}_{S}$ if and only if
$\nu_{S}^{\\{1\\}}(R)=S$. Lemma 3.1 now implies

$f(S)=(f\circ\nu_{S}^{\\{1\\}})(R)=(\nu_{f(S)}^{\\{1\\}}\circ
f)(R)=\nu_{f(S)}^{\\{1\\}}(f(R))$

and thus $f(R)\subseteq\mathsf{Eq}_{f(S)}$.

We are now ready to prove one of the implications of the claimed equivalence:

######  Lemma 3.5.

Let $\mathcal{C}$ be a $k$-ary coherent configuration, $X,Y\in F(\mathcal{C})$
two distinct fibers and $S\in\mathcal{C}|_{2}[X,Y]$ a disjoint union of stars
between $X$ and $Y$. If $\mathcal{C}\setminus X$ is separable, then so is
$\mathcal{C}$.

######  Proof 3.6.

Assume that $\mathcal{C}\setminus X$ is separable and let
$f\colon\mathcal{C}\to\mathcal{D}$ be an algebraic isomorphism. Then $f$
restricts to an algebraic isomorphism $f_{0}\colon\mathcal{C}\setminus
X\to\mathcal{D}\setminus f(X)$, which is induced by a combinatorial
isomorphism $\varphi_{0}\colon\mathcal{C}\setminus X\to\mathcal{D}\setminus
f(X)$ because $\mathcal{C}\setminus X$ is separable. We extend this map to all
of $\mathcal{C}$ by defining

$\displaystyle\varphi\colon V(\mathcal{C})$ $\displaystyle\to V(\mathcal{D}),$
$\displaystyle x$ $\displaystyle\mapsto\begin{cases}\varphi_{0}(x)&\text{if
}x\notin X,\\\ (\nu_{f(S)}\circ\varphi_{0})(y)&\text{if }x\in X\text{ and
}x=\nu_{S}(y)\text{ for some }y\in Y.\end{cases}$

We claim that $\varphi$ is a well-defined combinatorial isomorphism inducing
$f$.

To see well-definedness, we need to argue that the definition of $\varphi(x)$
for vertices $x\in X$ does not depend on the choice of its $\nu_{S}$-preimage
$y\in Y$. But indeed, if $\nu_{S}(y)=\nu_{S}(y^{\prime})$, then
$yy^{\prime}\in\mathsf{Eq}_{S}$. By Lemma 3.3, it holds that
$f(\mathsf{Eq}_{S})=\mathsf{Eq}_{f(S)}$. As $\varphi_{0}$ induces $f_{0}$, we
get $\varphi_{0}(y)\varphi_{0}(y^{\prime})\in\mathsf{Eq}_{f(S)}$. But this
means that $\nu_{f(S)}(\varphi_{0}(y))=\nu_{f(S)}(\varphi_{0}(y^{\prime}))$
which implies that $\varphi$ is well-defined. Moreover, it is a bijection as
$\varphi_{0}$ is a bijection and $\varphi|_{X}\colon X\to f(X)$ is a
bijection. To show that $\varphi$ induces $f$, consider a basis relation
$\nu_{S}^{I}(R)\in\mathcal{C}$ where $R\in\mathcal{C}\setminus X$ and $I$ is a
subset of the $Y$-components of $X$. Applying $\varphi$ to this basis relation
yields

$\displaystyle\varphi(\nu_{S}^{I}(R))$
$\displaystyle=\left(\varphi\circ\nu_{S}^{I}\right)(R).$ Using the definition
of $\varphi$, this is equal to
$\displaystyle=\left(\nu_{f(S)}^{I}\circ\varphi_{0}\right)(R)=\left(\nu_{f(S)}^{I}\circ
f_{0}\right)(R)=\left(\nu_{f(S)}^{I}\circ f\right)(R),$ which, by Lemma 3.3,
is equal to
$\displaystyle=\left(f\circ\nu_{S}^{I}\right)(R)=f\left(\nu_{S}^{I}(R)\right).$

This proves that $\varphi$ induces $f$ and thus in particular that $\varphi$
is a combinatorial isomorphism. Thus, $\mathcal{C}$ is separable.

Next, we want to prove the converse of Lemma 3.5, which will allow us to
eliminate all disjoint unions of stars without affecting separability of the
configuration. For this, we need one auxiliary lemma:

######  Lemma 3.7.

For every $k$-ary coherent configuration $\mathcal{C}$, fiber $Y\in
F(\mathcal{C})$ and every union of basis relations
$E\in\left(\mathcal{C}|_{2}[Y]\right)^{\cup}$ which forms an equivalence
relation on $Y$, there exists an extension $\mathcal{C}_{E}^{\star}$ of
$\mathcal{C}$ by a single fiber $X$ such that the interspace
$\mathcal{C}_{E}^{\star}[X,Y]$ contains a disjoint union of stars $S$
satisfying $E=\mathsf{Eq}_{S}$. Moreover, this extension is unique up to
combinatorial isomorphism.

Furthermore, the construction satisfies the following properties:

  1. 1.

For every $\mathcal{C}$ and $E$ as above, we have
$(\mathcal{C}|_{2})_{E}^{\star}=\left.\left(\mathcal{C}_{E}^{\star}\right)\right|_{2}$.

  2. 2.

For every configuration $\mathcal{C}$ and every interspace $\mathcal{C}[X,Y]$
that contains a disjoint union of stars $S$, we have
$\mathcal{C}\cong(\mathcal{C}\setminus X)_{\mathsf{Eq}_{S}}^{\star}$.

######  Proof 3.8.

Define $X\coloneqq Y/E$ as the quotient of $Y$ by the equivalence relation
$E$, and $\nu_{S}\colon Y\to X$ as the natural projection. Now, we define
$V(\mathcal{C}_{E}^{\star})\coloneqq V(\mathcal{C})\mathbin{\dot{\cup}}X$, and
extend $\nu_{S}$ to all of $V(\mathcal{C}_{E}^{\star})$ by letting it act as
the identity on every fiber besides $Y$. Once again, we write $\nu_{S}^{I}$
for the map $V(\mathcal{C}_{E}^{\star})^{k}\to V(\mathcal{C}_{E}^{\star})^{k}$
defined by $\nu_{S}^{I}(y_{1},\dots,y_{k})\coloneqq(z_{1},\dots,z_{k})$, where
$z_{i}\coloneqq\nu_{S}^{I}(y_{i})$ for all $i\in I$ and $z_{i}\coloneqq y_{i}$
for all $i\notin I$. To simplify notation, we also abbreviate this map as
$(I)$.

By Lemma 3.1, all of the sets $R^{(I)}$ with $R\in\mathcal{C}$ and $I$ a
subset of the $Y$-components of $R$ must be basis relations of
$\mathcal{C}_{E}^{\star}$ if we want to make $\mathcal{C}_{E}^{\star}$
coherent. Hence, we can only define the basis relations of
$\mathcal{C}_{E}^{\star}$ in a unique way:

$\mathcal{C}_{E}^{\star}\coloneqq\left\\{R^{(I)}\colon
R\in\mathcal{C},I\subseteq[k],R_{I}\subseteq Y^{|I|}\right\\}.$

######  Claim 4.

$\mathcal{C}_{E}^{\star}$ is a $k$-ary rainbow with
$\mathcal{C}_{E}^{\star}\setminus X=\mathcal{C}$. The fact that every
$k$-tuple in $\mathcal{C}_{E}^{\star}$ is contained in at least one of these
basis relations follows from surjectivity of $\nu_{S}$. To see that every two
distinct basis relations are disjoint, we note that for every basis relation
$R^{(I)}\in\mathcal{C}_{E}^{\star}$, the set $I$ can be reconstructed as the
set of $X$-components of $R^{(I)}$. This implies that if
$R^{(I)}\cap{R^{\prime}}^{(I^{\prime})}\neq\emptyset$, then $I=I^{\prime}$.
For every $k$-tuple ${\mathbf{x}}$ in this intersection, we can write
${\mathbf{x}}={\mathbf{y}}^{(I)}=({\mathbf{y}}^{\prime})^{(I)}$ for some
${\mathbf{y}}\in R$ and ${\mathbf{y}}\in R^{\prime}$. Then for every $i\in I$,
we have $\nu_{S}(y_{i})=x_{i}=\nu_{S}(y_{i}^{\prime})$ and thus
$y_{i}y_{i}^{\prime}\in E$.

Now, fix some $i\in I$, and let $R_{i}$ be the basis relation containing
${\mathbf{y}}\frac{y_{i}^{\prime}}{i}$. For all $j\neq i$, we set

$R_{j}\coloneqq\\{{\mathbf{z}}\in V(\mathcal{C})\colon z_{i}z_{j}\in E\\}.$

The sets $R_{j}$ are unions of basis relations, and we have

$p\left(R;R_{1},\dots,R_{k}\right)\geq 1,$

because ${\mathbf{y}}\frac{y_{i}^{\prime}}{j}\in R_{j}$ for all $j\in[k]$. But
as the relations $R_{j}$ for $j\neq i$ also ensure that any witness $z$ to
this inequality must satisfy $y_{i}z\in E$, we get that for every
${\mathbf{y}}\in R$, there is some $z\in V(\mathcal{C})$ with $y_{i}z\in E$
such that ${\mathbf{y}}\frac{z}{i}\in R_{i}$. We can iterate this construction
with $R_{i}$ instead of $R$ and a different $i\in I$. If we do this for all
$i\in I$, we finally get that for every ${\mathbf{y}}\in R$ and every $i\in
I$, there is some $z_{i}\in V(\mathcal{C})$ such that $y_{i}z_{i}\in E$ and
furthermore, these $z_{i}$ satisfy
${\mathbf{y}}\left(\frac{z_{i}}{i}\right)_{i\in I}\in R^{\prime}$. But this
means $R^{(I)}\subseteq{R^{\prime}}^{(I)}$ and by symmetry of the argument,
$R^{(I)}={R^{\prime}}^{(I)}$.

This concludes the proof that the basis relations $R^{(I)}$ form a partition
of $V(\mathcal{C}_{E}^{\star})^{k}$. The fact that this partition is
compatible with equality types follows from the fact that for
${\mathbf{x}}={\mathbf{y}}^{(I)}\in R^{(I)}$ we have $x_{i}=x_{j}$ if and only
if either $i,j\in I$ and $y_{i}y_{j}\in E$ or $i,j\notin I$ and $y_{i}=y_{j}$.
The fact that the partition is compatible with permutations follows from the
observation that
$\bigl{(}R^{(I)}\bigr{)}^{\sigma}=(R^{\sigma})^{(I^{\sigma})}$ for every
permutation $\sigma$ on $[k]$. This concludes the proof that
$\mathcal{C}_{E}^{\star}$ is a $k$-ary rainbow. As furthermore
$R^{(\emptyset)}=R$ for all $R\in\mathcal{C}$, this rainbow extends
$\mathcal{C}$.

In order to finish the proof that $\mathcal{C}_{E}^{\star}$ is a $k$-ary
coherent configuration, it remains to show that the intersection numbers of
$\mathcal{C}_{E}^{\star}$ are well-defined, that is, independent on the
specific choice of vertex tuple in the basis relation. For this, we write
$R\sim_{I}R^{\prime}$ for basis relations $R,R\in\mathcal{C}$ if
$R^{(I)}={R^{\prime}}^{(I)}$. Moreover, we write

$R/I\coloneqq\bigcup_{\begin{subarray}{c}R^{\prime}\in\mathcal{C}\\\
R^{\prime}\sim_{I}R\end{subarray}}R^{\prime}.$

Now, to prove coherence of $\mathcal{C}_{E}^{\star}$, let
$R^{(I)},T_{1}^{(I_{1})},\dots,T_{k}^{(I_{k})}\in\mathcal{C}_{E}^{\star}$ be
arbitrary basis relations and pick some representative
${\mathbf{x}}={\mathbf{y}}^{(I)}\in R^{(I)}$ with ${\mathbf{y}}\in R$. For
every $z\in V(\mathcal{C})$, we then have

${\mathbf{x}}\frac{z}{i}={\mathbf{y}}^{(I)}\frac{z}{i}=\left({\mathbf{y}}\frac{z}{i}\right)^{(I\setminus\\{i\\})}.$

This means that ${\mathbf{x}}\frac{z}{i}\in T_{i}^{(I_{i})}$ if and only if
$I_{i}=I\setminus\\{i\\}$ and ${\mathbf{y}}\frac{z}{i}\in
T_{i}[\sim_{I_{i}}]$. For all $x\in X$ and $y\in Y$ such that $x=\nu_{S}(y)$,
the analogous calculation instead yields

${\mathbf{x}}\frac{x}{i}={\mathbf{y}}^{(I)}\frac{\nu_{S}(y)}{i}=\left({\mathbf{y}}\frac{y}{i}\right)^{(I\cup\\{i\\})}.$

This means that ${\mathbf{x}}\frac{x}{i}\in T_{i}^{(I_{i})}$ if and only if
$I_{i}=I\cup\\{i\\}$ and ${\mathbf{y}}\frac{y}{i}\in T_{i}[\sim_{I_{i}}]$. As
one of the $S$-neighbors of $x$ satisfies this last condition if and only if
every $S$-neighbor does, we overcount the number of such $x\in X$ by a factor
of $p\left(X;S\right)$ if we count the number of such $y\in Y$ instead.

In total, this means that if for some ${\mathbf{x}}\in R^{(I)}$ we define

$p\left({\mathbf{x}};T_{1}^{(I_{1})},\dots,T_{k}^{(I_{k})}\right)\coloneqq\left|\left\\{y\in
V(\mathcal{C})\colon{\mathbf{x}}\frac{y}{i}\in R_{i}\text{ for all
}i\in[k]\right\\}\right|,$

then this intersection number can be expressed as

$\displaystyle
p\left({\mathbf{x}};T_{1}^{(I_{1})},\dots,T_{k}^{(I_{k})}\right)=\begin{cases}p\left(R;T_{1}[\sim_{I_{1}}],\dots,T_{k}[\sim_{I_{k}}]\right)&\text{if
}I_{i}=I\setminus\\{i\\}\text{ for all }i\in[k],\vspace{2mm}\\\
\displaystyle\frac{p\left(R;T_{1}[\sim_{I_{1}}],\dots,T_{k}[\sim_{I_{k}}]\right)}{p\left(X;S\right)}&\text{if
}I_{i}=I\cup\\{i\\}\text{ for all }i\in[k],\vspace{2mm}\\\
0&\text{otherwise.}\end{cases}$ (1)

As the right-hand side of Equation 1 does not depend on ${\mathbf{x}}$ but
only on the basis relation $R$ containing ${\mathbf{y}}$ which can be chosen
to be the same for all ${\mathbf{x}}={\mathbf{y}}^{(I)}\in R^{(I)}$, the
intersection number
$p\left(R^{(I)};T_{1}^{(I_{1})},\dots,T_{k}^{(I_{k})}\right)$ is well-defined.
This proves coherence of $\mathcal{C}_{E}^{\star}$.

Property 1 follows from the observation that for all $I\subseteq[k]$, the
$[2]$-face of $R^{(I)}$ is given by $(R_{[2]})^{(I\cap[2])}$. Property 2
follows from uniqueness of the extension.

Now, we are ready to prove the converse of Lemma 3.5.

######  Lemma 3.9.

Let $\mathcal{C}$ be a $k$-ary coherent configuration, $X,Y\in F(\mathcal{C})$
two distinct fibers, and $S\in\mathcal{C}|_{2}[X,Y]$ a disjoint union of stars
between $X$ and $Y$.

  1. 1.

If $\mathcal{C}$ is separable, so is $\mathcal{C}\setminus X$.

  2. 2.

If $\mathcal{C}$ is $2$-induced, so is $\mathcal{C}\setminus X$.

######  Proof 3.10.

We start with the first claim. Assume that $\mathcal{C}$ is separable and let
$f_{0}\colon\mathcal{C}\setminus X\to\mathcal{D}$ be an arbitrary algebraic
isomorphism. Then $E\coloneqq f_{0}(\mathsf{Eq}_{S})$ is a union of $2$-ary
basis relations in $\mathcal{D}[f_{0}(Y)]$ which forms an equivalence
relation. We want to construct an extension
$f\colon\mathcal{C}\to\mathcal{D}_{E}^{\star}$ of $f$. Then, by separability
of $\mathcal{C}$, we would find a combinatorial isomorphism $\varphi$ that
induces $f$ and whose restriction to $\mathcal{C}\setminus X$ induces $f_{0}$.

For this, recall that the basis relations of $\mathcal{C}$ are all of the form
$R^{(I)}=\nu_{S}^{I}(R)$ with $R\in\mathcal{C}\setminus X$ and $I$ a subset of
the $Y$-components of $R$; and the basis relations of
$\mathcal{D}_{E}^{\star}$ are of the form $T^{(I)}=\nu_{f(S)}^{I}(T)$ for
$T\in\mathcal{D}$ and $I$ a subset of the $f(Y)$-components of $T$. We define
the extension $f$ of $f_{0}$ by

$f\left(R^{(I)}\right)\coloneqq\left(f_{0}(R)\right)^{(I)}.$

######  Claim 5.

The map $f$ is a well-defined extension of $f_{0}$. To see that this map is
well-defined, note that the set $I$ is precisely the set of $X$-components of
$R^{(I)}$ and is thus determined by the basis relation. Thus, we only need to
show that whenever $R^{(I)}={R^{\prime}}^{(I)}$, then also
$(f_{0}(R))^{(I)}=\left(f_{0}(R^{\prime})\right)^{(I)}$. The former is the
case if and only if $R$ and $R^{\prime}$ can be transformed into one another
by replacing for all ${\mathbf{x}}\in R$ the $X$-components of ${\mathbf{x}}$
by one or multiple $\mathsf{Eq}_{S}$-equivalent components. As the analogous
claim is true in $\mathcal{D}_{E}^{\star}$ and as $f_{0}$ sends
$\mathsf{Eq}_{S}$ to $\mathsf{Eq}_{f(S)}$ by construction, it follows that $f$
is well-defined. Moreover, $f$ extends $f_{0}$, as for $I=\emptyset$, we get
$f(R)=f_{0}(R)$ for all $R\in\mathcal{C}\setminus X$.

######  Claim 6.

The map $f$ is an algebraic isomorphism. The intersection numbers of both
$\mathcal{C}\cong(\mathcal{C}\setminus X)_{\mathsf{Eq}_{S}}^{\star}$ and
$\mathcal{D}_{E}^{\star}$ are determined in terms of those of
$\mathcal{C}\setminus X$ and $\mathcal{D}$ by Equation (1). To see that $f$
preserves the right-hand side of this formula, recall that we defined

$R/I=\bigcup_{\begin{subarray}{c}R^{\prime}\in\mathcal{C}\setminus X\\\
R^{(I)}=(R^{\prime})^{(I)}\end{subarray}}R^{\prime}.$

It now remains to show that $f_{0}(R/I)=f_{0}(R)/I$ for all
$R\in\mathcal{C}\setminus X$ and every subset $I$ of the $Y$-components of
$R$.

We again use the observation that $R^{(I)}=(R^{\prime})^{(I)}$ if and only if
$R$ can be obtained from $R^{\prime}$ by replacing some of its $Y$-components
by $\mathsf{Eq}_{S}$-neighbors, and that the analogous statement is true in
$\mathcal{D}_{E}^{\star}$ with respect to $\mathsf{Eq}_{f(S)}$. Therefore, we
have $R^{(I)}=(R^{\prime})^{(I)}$ if and only if
$\left(f_{0}(R)\right)^{(I)}=\left(f_{0}(R^{\prime})\right)^{(I)}$. This
implies $f(R/I)=f(R)/I$ and thus that $f$ preserves intersection numbers.

We have now successfully extended the algebraic isomorphism
$f_{0}\colon\mathcal{C}\setminus X\to\mathcal{D}$ to an algebraic isomorphism
$f\colon\mathcal{C}\to\mathcal{D}_{E}^{\star}$. Because $\mathcal{C}$ is
separable, $f$ is induced by a combinatorial isomorphism $\varphi$ which
restricts to an isomorphism $\varphi_{0}$ inducing $f_{0}$.

For the second claim, assume that $\mathcal{C}$ is $2$-induced. To show that
$\mathcal{C}\setminus X=\operatorname{WL}_{k}((\mathcal{C}\setminus X)|_{2})$,
we first note that the left-hand side is a $k$-ary coherent configuration on
$V(\mathcal{C})\setminus X$ that is at least as fine as $(\mathcal{C}\setminus
X)|_{2}$ and thus also at least as fine as
$\operatorname{WL}_{k}((\mathcal{C}\setminus X)|_{2})$. For the converse,
consider the $k$-ary coherent configuration
$\mathcal{C}^{\prime}\coloneqq\operatorname{WL}_{k}((\mathcal{C}\setminus
X)|_{2})_{\mathsf{Eq}_{S}}^{\star}$. By choosing the obvious bijection between
the fiber $X\in F(\mathcal{C})$ and the additional fiber of
$\mathcal{C}^{\prime}$, we can assume that $\mathcal{C}^{\prime}$ is a $k$-ary
coherent configuration on $V(\mathcal{C})$, which is furthermore at most as
fine as $\mathcal{C}$. Now, note that

$\mathcal{C^{\prime}}|_{2}=\Bigl{(}\operatorname{WL}_{k}\bigl{(}(\mathcal{C}\setminus
X)|_{2}\bigr{)}\big{|}_{2}\Bigr{)}_{\mathsf{Eq}_{S}}^{\star}=\bigl{(}(\mathcal{C}\setminus
X)|_{2}\bigr{)}_{\mathsf{Eq}_{S}}^{\star}=(\mathcal{C}\setminus
X)_{\mathsf{Eq}_{S}}^{\star}\big{|}_{2}=\mathcal{C}|_{2},$

where the first and third equality follow from Property 1 of Lemma 3.7, the
second equality follows from the fact that $\mathcal{C}\setminus X$ is a
$k$-ary coherent configuration, and the last equality follows from Property 2
of Lemma 3.7. As $\mathcal{C}$ is $2$-induced, this yields
$\mathcal{C}^{\prime}\preceq\operatorname{WL}_{k}(\mathcal{C}|_{2})=\mathcal{C}$
and thus $\mathcal{C}=\mathcal{C}^{\prime}$. Finally,

$\mathcal{C}\setminus X=\mathcal{C}^{\prime}\setminus
X=(\operatorname{WL}_{k}((\mathcal{C}\setminus X)|_{2}))_{E}^{\star}\setminus
X=\operatorname{WL}_{k}((\mathcal{C}\setminus X)|_{2})$

shows that $\mathcal{C}\setminus X$ is $2$-induced.

Lemma 3.5 together with Lemma 3.9 allows us to remove fibers from coherent
configurations containing a disjoint union of stars without affecting the
separability of the configuration. Thus, we have reduced the separability
problem for arbitrary $k$-ary coherent configurations to the same problem for
star-free configurations. Furthermore by Lemma 3.9, this process preserves
$2$-inducedness of a configuration. Thus, in order to solve the separability
problem for $2$-induced $k$-ary coherent configurations, it only remains to
consider $2$-induced star-free configurations. This simultaneously generalizes
the elimination of interspaces containing a matching and the elimination of
fibers of size $2$ from [16].

###  3.2 Structure of $k$-ary coherent configurations of color multiplicity 5

$K_{1}$

$K_{2}$

$K_{3}$

$\overrightarrow{C}_{3}$

$K_{4}$

$F_{4}$

$C_{4}$

$\overrightarrow{C}_{4}$

$K_{5}$

$C_{5}$

$\overrightarrow{C}_{5}$

Figure 2: The complete list of $2$-ary coherent configurations on a single
fiber of order up to $4$ from [16], and the three $2$-ary coherent
configurations on a single fiber of order $5$ from [39].

A list of all isomorphism types of $2$-ary coherent configurations on a single
fiber of order at most $5$ is known [16, 39], see Figure 2. Furthermore, the
authors of [16] also give a complete list of possible interspaces between
fibers of order up to $4$. Here, it is always possible that the interspace
$\mathcal{C}[X,Y]$ is _uniform_ , meaning that it consists of only a single
basis relation $X\times Y$. Uniform interspaces are usually easy to handle and
the other interspace types are the more interesting ones. As we already
eliminated interspaces containing a disjoint union of stars, Figure 3 contains
only the two remaining non-uniform and star-free interspaces.

In [16, Lemma 5.2], it was shown that both of these interspaces enforce the
existence of a matching in both incident fibers. These matchings are denoted
by dotted lines in Figure 3.

As there can be no non-uniform interspaces between fibers of coprime orders
[16, Lemma 3.1], we are thus only missing an enumeration of the non-uniform
star-free interspaces between two fibers of order $5$ each. However, as every
such interspace must contain a relation which has degree $2$ in both fibers,
the only candidate for such an interspace is the $C_{10}$, the interspace
containing a basis relation forming a $10$-cycle between the two fibers. But
this $10$-cycle induces a matching between opposite vertices. Thus, in a star-
free $2$-ary coherent configuration of color multiplicity $5$, there can be no
non-uniform interspaces incident to any fibers of order $5$.

$2K_{2,2}$

$C_{8}$

Figure 3: All non-uniform and star-free interspace types between two fibers of
order up to $5$. In each case, one of the basis relations between the two
fibers is missing and can be reconstructed as the complement of the one drawn.

In the $k$-dimensional case, interspaces are generally not between two, but
between $k$ fibers and their enumeration and analysis is more complicated. But
as we are only dealing with $2$-induced $k$-ary coherent configuration, the
two-dimensional interspaces suffice for our purposes.

We need the following fact about star-free (and indeed even matching-free)
configurations:

######  Lemma 3.11 ([16, Lemma 6.2]).

In a star-free $2$-ary coherent configuration, no two distinct interspaces of
type $C_{8}$ can be incident to a common fiber.

This allows us to prove the following generalization of [16, Lemma 7.1]:

######  Lemma 3.12.

Let $\mathcal{C}$ be a star-free $2$-ary coherent configuration of color
multiplicity $5$. If $f\colon\mathcal{C}\to\mathcal{D}$ is an algebraic
isomorphism, then there exists a combinatorial isomorphism $\varphi\colon
V(\mathcal{C})\to V(\mathcal{D})$ which induces $f$ on every fiber.

######  Proof 3.13.

As every $2$-ary coherent configuration with at most $8$ vertices is separable
[16], we can pick for every $C_{8}$-interspace $\mathcal{C}[X,Y]$ a
combinatorial isomorphism $\varphi_{X,Y}\colon X\cup Y\to X^{f}\cup Y^{f}$
which induces $f|_{\mathcal{C}[X\cup Y]}$ and for every fiber $Z$ not incident
to a $C_{8}$-interspace an isomorphism $\varphi_{Z}\colon Z\to Z^{f}$ inducing
$f|_{\mathcal{C}[X]}$.

By Lemma 3.11, the domains of these partial combinatorial isomorphisms form a
partition of $V(\mathcal{C})$. Thus, we can combine these bijections to get a
total bijection $\varphi\colon V(\mathcal{C})\to V(\mathcal{D})$. It remains
to show that $\varphi$ is a combinatorial isomorphism on every interspace.
This is immediate on uniform interspaces and true by construction on
interspaces of type $C_{8}$.

The only remaining interspace type is thus $2K_{2,2}$. But here, the
interspace is uniquely determined by its isomorphism-type and the matchings it
induces in the incident fibers. On such interspaces $\varphi$ thus either
induces $f$ or switches the two basis relations. In both cases, $\varphi$ is a
combinatorial isomorphism.

We call an algebraic automorphism $f$ of a $k$-ary coherent configuration
$\mathcal{C}$ _strict_ if it fixes every fiber, i.e., satisfies $f(X)=X$ for
every fiber $X\in F(\mathcal{C})$. The strict algebraic automorphisms of
$\mathcal{C}$ form a group, which we denote by $\mathbb{A}(\mathcal{C})$. Now,
we get the following reformulation of separability:

######  Lemma 3.14.

A star-free and $2$-induced $k$-ary coherent configuration $\mathcal{C}$ of
color multiplicity $5$ is separable if and only if every strict algebraic
automorphism is induced by a combinatorial automorphism.

######  Proof 3.15.

The forward implication is immediate. For the converse implication, let
$f\colon\mathcal{C}\to\mathcal{D}$ be an algebraic isomorphism. Then $f$
induces an algebraic isomorphism
$f|_{2}\colon\mathcal{C}|_{2}\to\mathcal{D}|_{2}$. By Lemma 3.12, we find a
combinatorial isomorphism $\varphi\colon V(\mathcal{C}|_{2})\to
V(\mathcal{D}|_{2})$ which induces $f|_{2}$ on every fiber. Because
$\mathcal{C}$ is $2$-induced, this map is also a combinatorial isomorphism
between $\mathcal{C}$ and $\mathcal{D}$ and thus induces an algebraic
isomorphism $g_{\varphi}\colon\mathcal{C}\to\mathcal{D}$ such that
$f(X)=g_{\varphi}(X)$ for every fiber $X\in\mathcal{C}$. Now,
$g_{\varphi}^{-1}\circ f$ is a strict algebraic automorphism of $\mathcal{C}$
and is thus induced by some combinatorial automorphism $\psi$. But then $f$ is
induced by $\varphi\circ\psi$, which proves separability of $\mathcal{C}$.

###  3.3 Strict algebraic automorphisms

In this section, we give a polynomial time algorithm to decide whether every
strict algebraic automorphism of a $k$-ary coherent configuration
$\mathcal{C}$ is induced by a combinatorial automorphism.

We will heavily make use of the fact that the graph isomorphism problem is
polynomial-time solvable for graphs of bounded color multiplicity:

######  Lemma 3.16 ([6, 17]).

Isomorphism of $k$-ary relational structures of order $n$ and color
multiplicity $c$ can be decided in time $O_{k,c}(n^{O(k)})$. Moreover, a
generating set of $\operatorname{Aut}(\mathfrak{A})$ for of a $k$-ary
relational structure $\mathfrak{A}$ of order $n$ and color multiplicity $c$
can also be computed in the same time bounds.

By encoding the algebraic structure of a $k$-ary coherent configuration into a
graph $G_{\mathcal{C}}$ such that the strict algebraic automorphisms of
$\mathcal{C}$ become automorphisms of $G_{\mathcal{C}}$, we obtain the
following:

######  Lemma 3.17.

There is an algorithm running in time $O_{k,c}(n^{O(k)})$ that, given a
$k$-ary coherent configuration $\mathcal{C}$ of order $n$ and color
multiplicity $c$, computes a generating set of $\mathbb{A}(\mathcal{C})$.

######  Proof 3.18.

We construct a graph $G_{\mathcal{C}}$ of bounded color multiplicity and order
$O(n^{k})$ whose automorphism group is isomorphic to
$\mathbb{A}(\mathcal{C})$. Lemma 3.16 then yields the claim.

For this, we call a $k$-tuple ${\mathbf{R}}=(R_{1},\dots,R_{k})$ of basis
relations of $\mathcal{C}$ _compatible_ if for some basis relation
$R\in\mathcal{C}$ we have $p\left(R;R_{1},\dots,R_{k}\right)>0$. Let
$\mathcal{C}^{(k)}$ be the collection of all such tuples. Because for every
compatible tuple ${\mathbf{R}}$ of basis relations there must exist some
${\mathbf{x}}\in V(\mathcal{C})^{k}$ and $x^{\prime}\in V(\mathcal{C})$ such
that ${\mathbf{x}}\frac{x^{\prime}}{i}\in R_{i}$ for all $i\in[k]$, there are
at most $n^{k+1}$ compatible tuples, and these can be found in time $n^{O(k)}$
by enumerating all such pairs $({\mathbf{x}},x^{\prime})$ noting which
compatible tuple of basis relations they correspond to.

Now, we define the graph $G_{\mathcal{C}}$ on the vertex set
$V(G_{\mathcal{C}})\coloneqq\mathcal{C}\mathbin{\dot{\cup}}\mathcal{C}^{(k)}$
by putting in the following labeled edges:

  * •

connect $R$ and ${\mathbf{R}}$ with an edge labeled
$p\left(R;{\mathbf{R}}\right)$,

  * •

connect $R$ and ${\mathbf{R}}$ with an edge labeled $\\{i\in[k]\colon
R_{i}=R\\}$,

Finally, we define a vertex coloring on $G_{\mathcal{C}}$:

  * •

color each basis relation $R$ using the tuple $(R_{\\{i\\}})_{i\in[k]}$ of
fibers of its components,

  * •

color each compatible tuple of basis relations ${\mathbf{R}}$ using the tuple
of colors we assigned to its components.

This graph can clearly be constructed in time $n^{O(k)}$ and has order
$n^{O(k)}$.

Because the fibers of $\mathcal{C}$ have order at most $c$, there can be at
most $c^{k}$ basis relations sharing the same color. Thus, the number of
compatible tuples of basis relations sharing a color is bounded by
$(c^{k})^{k}=c^{k^{2}}\in O_{k,c}(1)$. Moreover, its automorphism group is as
required: each automorphism is determined by how it permutes the basis
relations, the edge-colors ensure that this automorphism is an algebraic
automorphism, and the vertex-colors ensure strictness.

As the collection of those strict algebraic automorphisms which are induced by
combinatorial ones forms a subgroup of $\mathbb{A}(\mathcal{C})$, it now
suffices to check whether each of the polynomially many elements of the
generating set of $\mathbb{A}(\mathcal{C})$ is induced by a combinatorial
automorphism. This can also be checked in polynomial time:

######  Lemma 3.19.

There is an algorithm running in time $O_{k,c}(n^{O(k)})$ that, given a
$k$-ary coherent configuration $\mathcal{C}$ of color multiplicity $c$ and a
strict algebraic automorphism $f\in\mathbb{A}(\mathcal{C})$, outputs whether
$f$ is induced by a combinatorial automorphism.

######  Proof 3.20.

Let $\mathfrak{C}$ be an arbitrary colored variant of $\mathcal{C}$ and
$\mathfrak{C}^{f}$ another colored variant such that $f$ becomes a color-
preserving map between the $k$-ary color classes of these two structures.
Combinatorial automorphisms inducing $f$ now naturally correspond to
isomorphisms between $\mathfrak{C}$ and $\mathfrak{C}^{f}$, meaning that $f$
is induced by a combinatorial automorphism if and only if
$\mathfrak{C}\cong\mathfrak{C}^{f}$. As $\mathcal{C}$ has bounded color
multiplicity, so does $\mathfrak{C}$. Thus, we can decide the latter in the
required time by Lemma 3.16.

######  Corollary 3.21.

There is an algorithm running in time $O_{k,c}(n^{O(k)})$ that, given a
$k$-ary coherent configuration $\mathcal{C}$ of color multiplicity $c$, either

  1. 1.

outputs a $\varphi\in\mathbb{A}(\mathcal{C})$ which not induced by a
combinatorial automorphism, or

  2. 2.

correctly returns that no such automorphisms exist.

This allows us to finally prove our first main theorem: *

######  Proof 3.22.

In a first step, we run $k\text{-}\mathrm{WL}$ on $G$ to get the $2$-induced
configuration $\mathcal{C}\coloneqq\operatorname{WL}_{k}(G)$. By Lemma 2.2, it
remains to decide whether $\mathcal{C}$ is separable. Now, we eliminate
disjoint unions of stars using Lemma 3.5, and Lemma 3.9, while maintaining
$2$-inducedness of $\mathcal{C}$. By Lemma 3.14, it remains to decide whether
every strict algebraic automorphism is induced by a combinatorial one. This
can finally be checked within the stated runtime by Corollary 3.21. If $G$ is
not identified by $k\text{-}\mathrm{WL}$, this algorithm also yields a strict
algebraic automorphism $f$ which is not induced by a combinatorial one.

By adding back all interspaces containing a disjoint union of stars, we can
extend $f$ to an algebraic isomorphism
$\widehat{f}\colon\operatorname{WL}_{k}(G)\to\mathcal{D}$ 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}$.

##  4 Hardness

In this section, we prove hardness results that complement the positive
results in the previous section. We start by showing that, when the dimension
$k$ is considered part of the input, the $k$-$\mathrm{WL}$-equivalence problem
and the $k$-$\mathrm{WL}$-identification problem are co-NP-hard and NP-hard,
respectively. This is achieved via reductions from Tree-width, which is NP-
hard even over cubic graphs [9]. The reduction is based on the CFI-
construction, see Section 2.

*

######  Proof 4.1.

Tree-width is the problem to decide whether the tree-width of a given graph
$G$ is at most a given number $k$. This problem is NP-hard even over cubic
graphs [9]. By Lemma 2.4, we have $\operatorname{tw}(G)=\operatorname{WL-
dim}(\operatorname{CFI}(G,0))$. Thus, computing the tree-width of a cubic
graph $G$ reduces to computing the Weisfeiler-Leman dimension of its CFI-
graph. Because the CFI-graphs of cubic graphs have color multiplicity at most
four, and CFI-graphs of cubic graphs can be efficiently computed, the hardness
result for graphs of color multiplicity at most $4$ follows.

The claim for the class of simple graphs follows from the observation that we
can encode colors into gadgets we attach to every vertex, and that these
gadgets can be chosen such that they do not affect the Weisfeiler-Leman
dimension.

Because in the above proof, we could explicitly construct a non-isomorphic but
equivalent graph, this also yields:

######  Theorem 4.2.

The problem of deciding, for a given pair of graph $G$ and $H$ and a natural
number $k\geq 1$, whether $G\equiv_{k\text{-}\mathrm{WL}}H$, is co-NP-hard.

Now, we once again turn to the $k$-$\mathrm{WL}$-identification problem for a
fixed dimension $k\geq 2$, and show that both over uncolored simple graphs,
and over simple graphs of color multiplicity at most $4$, the problem is
P-hard under logspace-uniform AC0-reductions.

We reduce from the P-hard monotone circuit value problem MCVP [18]. 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 based one 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 multiplicity and
are difficult to analyze. Instead, we give a new construction of such gadgets
with color multiplicity $4$ based on the CFI-construction. 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.

###  4.1 One-way switches

In the following sections, we fix a dimension $k\geq 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$. We say that _a
pair of vertices is split_ if the two vertices are colored differently. We say
that $k$-$\mathrm{WL}$ splits a pair if the coloring computed by
$k$-$\mathrm{WL}$ splits the pair.

The fundamental property of the $k$-one-way switch is the following: whenever
the input pair $\\{y_{1},y_{2}\\}$ of the one-way switch is split,
$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, see Section 2.

We start by defining our base graph. Consider a wall graph consisting of $k-1$
rows of $k$ bricks each. Then, we attach a new vertex $v$ to the two upper
corner vertices of the first row. The resulting graph $B_{k}$ is depicted in
Figure 4.

$v$ Figure 4: The base graph $B_{6}$ of the CFI-graphs underlying our one-way
switches.

######  Lemma 4.3.

The graph $B_{k}$ has tree-width $k+1$, while $B_{k}-v$ has tree-width $k$.

######  Proof 4.4.

Because the tree-width of a graph is invariant under subdividing edges, we can
delete $v$ and directly connect the two upper corner vertices of $B_{k}$. Let
$B_{k}^{\prime}$ be the resulting graph.

For every positive integer $\ell$, let $G_{k,\ell}^{\prime}$ be the graph
obtained from a $k\times\ell$-grid graph by directly connecting two corners
that lie on a common side of length $\ell$. Then $G_{k,k+1}^{\prime}$ is a
minor of $B_{k}^{\prime}$ and thus
$\operatorname{tw}(B_{k}^{\prime})\geq\operatorname{tw}(G_{k,k+1}^{\prime})$.
Similarly, up to a subdivision of some edges, which does not affect the tree-
width, $B_{k}^{\prime}$ is a subgraph of $G_{k,2k+1}^{\prime}$. Thus,

$\operatorname{tw}(G_{k,k+1}^{\prime})\leq\operatorname{tw}(B_{k}^{\prime})\leq\operatorname{tw}(G_{k,2k+1}^{\prime}).$

It thus suffices to argue that $\operatorname{tw}(G_{k,\ell}^{\prime})=k+1$
for all $\ell>k$. Because adding a single vertex or edge to a graph increases
the tree-width by at most $1$, and the $k\times\ell$-grid graph has tree-width
$\min(k,\ell)$, we have $\operatorname{tw}(B_{k}-v)=k$ and
$\operatorname{tw}(G_{k,\ell}^{\prime})\leq k+1$.

For the matching lower bound, we use the theory of brambles [40]. Recall that
a bramble $\mathcal{B}$ of a finite graph $H$ is a collection of connected
subgraphs of $H$ such that every two subgraphs in $\mathcal{B}$ either
overlap, or are connected by an edge. The order of a bramble is the size of a
minimal hitting set, i.e., the smallest $k\in\mathbb{N}$ such that there exist
$k$ vertices $v_{1},\dots,v_{k}$ such that every set $B\in\mathcal{B}$
contains one of the vertices $v_{i}$. It turns out that the maximal order of a
bramble in $H$ is precisely one more than the tree-width of $H$ [40].

For the matching lower bound, it thus suffices to construct a bramble in
$G_{k,\ell}^{\prime}$ of order at least $k+2$. Let the vertex set of
$G_{k,\ell}^{\prime}$ be $[k]\times[\ell]$, with the extra edge connecting
$(1,1)$ to $(1,\ell)$. For each $i\in[k]\setminus\\{k\\}$ and
$j\in[\ell]\setminus\\{\ell\\}$, we define a set

$U_{i,j}\coloneqq\\{(a,b)\in([k]\setminus\\{k\\})\times([\ell]\setminus\\{\ell\\})\colon
a=i\text{ or }b=j\\}$

to be the union of the $i$-th row and $j$-th column, while excluding the
vertices from the last row or column. Further, we take the two sets

$R_{k}\coloneqq\\{k\\}\times[\ell]\quad\text{and}\quad
C_{\ell}\coloneqq([k]\setminus\\{1,k\\})\times\\{\ell\\}.$

Finally, we define our bramble to be

$\displaystyle\bigl{\\{}R_{k},C_{\ell}\bigr{\\}}$
$\displaystyle{}\cup\bigl{\\{}U_{i,j}\colon
i\in[k]\setminus\\{1,k\\},j\in[\ell]\setminus\\{\ell\\}\bigr{\\}}$
$\displaystyle{}\cup\Bigl{\\{}\bigl{(}U_{1,j}\cup\\{(1,\ell)\\}\bigr{)}\setminus\\{(1,i)\\}\colon
j\in[\ell]\setminus\\{\ell\\},i\in[\ell]\setminus\\{j\\}\bigr{\\}}.$

To argue that this bramble has order at least $k+2$, we need to show that it
does not admit a hitting set of order at most $k+1$, that is, we must argue
that for every choice of $k+1$ vertices there exists some set in the bramble
which contains none of the vertices. Assume for contradiction that $H\subseteq
V(G_{k,\ell}^{\prime})$ was such a hitting set. Because the sets $R_{k}$ and
$C_{\ell}$ are disjoint from all other sets, $H$ must contain at least one
vertex in each of these sets. Hence, only $k-1$ vertices remain to hit all
other sets in the bramble. These $k-1$ vertices must miss one of the first
$\ell-1$ columns, say column $j$. If they also miss one of the first $k-1$
rows, say row $i$, then they miss the set $U_{i,j}$. Otherwise, there is
precisely one vertex per row. Let $(1,i)$ be the vertex in the first row. But
then the set misses
$\bigl{(}U_{1,j}\cup\\{(1,\ell)\\}\bigr{)}\setminus\\{(1,i)\\}$.

Now, we are ready to construct our one-way switches.

######  Lemma 4.5 (compare [19, Lemma 14]).

For every $k\geq 2$, there is a colored graph $O^{k}$ of color multiplicity
$4$, called _$k$ -one-way switch_, with an input pair $\\{y_{1},y_{2}\\}$ and
an output pair $\\{x_{1},x_{2}\\}$ satisfying the following properties:

  1. 1.

The graph $O^{k}_{{\mathrm{split}}}$ obtained by splitting the input pair
$\\{y_{1},y_{2}\\}$ is identified by $k$-$\mathrm{WL}$.

  2. 2.

$k$-$\mathrm{WL}$ splits the output pair $\\{x_{1},x_{2}\\}$ of
$O^{k}_{{\mathrm{split}}}$.

  3. 3.

There is no automorphism of $O^{k}$ exchanging the output vertices $x_{1}$ and
$x_{2}$.

Furthermore, there are sets of positions in the bijective $(k+1)$-pebble game
between $O^{k}$ and itself, called _trapped_ and _twisted_ such that

  1. 4.

every trapped or twisted position is a partial isomorphism,

  2. 5.

Duplicator can avoid non-trapped positions from trapped ones and non-twisted
positions from twisted ones,

  3. 6.

for every trapped position ${\mathbf{a}}\mapsto{\mathbf{b}}$, the position
${\mathbf{a}}x_{1}\mapsto{\mathbf{b}}x_{1}$ is also trapped,111 If the
position ${\mathbf{a}}x_{1}\mapsto{\mathbf{b}}x_{1}$ contains more than $k+1$
pebbles, this means that every subposition on at most $k+1$ pebbles is trapped

  4. 7.

for every twisted position ${\mathbf{a}}\mapsto{\mathbf{b}}$, the position
${\mathbf{a}}x_{1}\mapsto{\mathbf{b}}x_{2}$ is also twisted,

  5. 8.

the positions $y_{1}y_{2}\mapsto y_{1}y_{2}$ and $y_{1}y_{2}\mapsto
y_{2}y_{1}$ are both trapped and twisted,

  6. 9.

every subposition of a trapped position is trapped, and every subposition of a
twisted position is twisted

######  Proof 4.6.

Let $O^{k}$ be the (untwisted) CFI-graph of $B_{k}$, but with a CFI-gadget of
degree $3$ added for the vertex $v$ instead of a gadget of degree $2$. This
leaves one outer pair of this gadget free which we use as our output pair
$\\{x_{1},x_{2}\\}$. Furthermore, we use one of the other two outer pairs of
this same CFI-gadget as the input pair $\\{y_{1},y_{2}\\}$.

Now, if we fix the output pair $\\{x_{1},x_{2}\\}$ by individualizing one of
the two vertices, the resulting graph corresponds to the usual CFI-graph of
$H$, while switching the pair $\\{x_{1},x_{2}\\}$ corresponds to the twisted
CFI-graph of $H$. In particular, as these graphs are not isomorphic, there is
no automorphism of $O^{k}$ switching the pair $\\{x_{1},x_{2}\\}$, which
proves Property 3.

Moreover, splitting the input pair $\\{y_{1},y_{2}\\}$ has the same effect to
the power of $k$-$\mathrm{WL}$ as removing one of the two edges incident to
$v$ in the base graph $B_{k}$ has. When removing this edge in the base graph,
the resulting graph is essentially equivalent to the CFI-graph of the
$k\times(k+1)$-wall graph with one corner vertex replaced by a CFI-gadget of
degree $3$ instead of $2$. Because exchanging the two vertices of the free
outer pair of this degree-3 gadget interchanges the twisted and untwisted CFI-
graphs over the base graph, and $k$-$\mathrm{WL}$ can distinguish CFI-graphs
from all other graphs, the resulting graph is identified by $k$-$\mathrm{WL}$.
This proves Property 1.

To show Property 2, we start the bijective $(k+1)$-pebble game in position
$x_{1}\mapsto x_{2}$. Then, Spoiler uses the usual strategy of pebbling a wall
which they then move from one side of the wall graph to the other. But because
the game started in position $x\mapsto x^{\prime}$, the two graphs the game is
played on differ in a twist which will finally force Duplicator to lose.

Now, consider again the original graph $O^{k}$ without splitting the input
pair. On this graph, we can extend every winning position for Duplicator in
the bijective $k$-pebble game between the untwisted CFI-graph
$\operatorname{CFI}(B_{k},0)$ and the twisted CFI-graph
$\operatorname{CFI}(B_{k},1)$ to a position in the bijective $k$-pebble game
between $O^{k}$ and itself which is compatible with $x_{1}\mapsto x_{2}$.
Similarly, we can extend every winning position for Duplicator in the
bijective $k$-pebble game between the untwisted CFI-graph
$\operatorname{CFI}(B_{k},0)$ and itself to a position between $O^{k}$ and
itself which is compatible with $x_{1}\mapsto x_{1}$.

We call the former positions _twisted_ and the latter positions _trapped_.
Properties 4, 6, 7 and 9 are then immediate, and Property 5 follows from Lemma
2.4 together with Lemma 4.3.

Because $v$ lies on a cycle in $B_{k}$, there exists an automorphism of
$\operatorname{CFI}(B_{k})$ which twists both outer pairs of the gadget
corresponding to $v$. Lifting this automorphism to $O^{k}$ yields an
automorphism switching $y_{1}$ and $y_{2}$ whilst fixing $x_{1}$ and $x_{2}$.
This proves Property 8.

###  4.2 From monotone circuits to graphs

We now reduce the monotone circuit value problem MCVP to the
$k$-$\mathrm{WL}$-identification problem. A monotone circuit $M$ is a circuit
consisting of input nodes, each of which has value either True or False, a
distinguished output node, and inner nodes, which are either $\and$\- or
$\mathrm{OR}$-nodes with two inputs each. We write $V(M)$ for the set of nodes
of $M$. With the monotone circuit $M$, we can associate the evaluation
function $\operatorname{val}_{M}\colon
V(M)\to\\{\textup{{True}},\textup{{False}}\\}$, which is defined in the
obvious way. The monotone circuit value problem MCVP is the following problem:
given a monotone circuit $M$ with output node $c$, decide whether
$\operatorname{val}_{M}(c)=\textup{{True}}$. This problem is known to be hard
for polynomial time [18].

$G_{\mathrm{OR}}$

$G_{\and}$

Figure 5: The gadgets $G_{\mathrm{OR}}$ and $G_{\and}$ encoding
$\mathrm{OR}$\- and $\and$-gates. We call the two pairs at the top their
_input pairs_ and their bottom pair their _output pair_.

Now, let $M$ be such 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}$ which will be split by $k\text{-}\mathrm{WL}$
if and only if $\operatorname{val}_{M}(a)=\textup{{False}}$. We use the two
graphs $G_{\mathrm{OR}}$ and $G_{\and}$ in Figure 5 as gadgets to replace the
logic gates in our construction of $G_{M}$. These gadgets both have two input
pairs and one output pairs such that exchanging the two output vertices by an
automorphism requires the two vertices of one (for $G_{\mathrm{OR}}$) or both
(for $G_{\and}$) input pairs to also be exchanged.

FalseFalseTrue$\land$$\lor$$M$$G_{\and}$$G_{\mathrm{OR}}$$\longrightarrow$$\longrightarrow$$\longrightarrow$$\longrightarrow$$\longrightarrow$$G_{M}$
Figure 6: A simple monotone circuit $M$ and the graph $G_{M}$ obtained from
it. The colors in $M$ are just for illustration purposes and not part of the
actual circuit.

We now start with the formal construction of $G_{M}$, which is depicted in
Figure 6. For every node $a$ of $M$, we add a pair of vertices
$\\{a_{1},a_{2}\\}$ forming a color class to $G_{M}$. To encode the input
valuation of the circuit, we split every pair $\\{a_{1},a_{2}\\}$
corresponding to an input node $a$ of value False.

For every $\and$-node $a\in V(M)$ with input nodes $b$ and $b^{\prime}$, we
add a freshly colored copy of the gadget $G_{\and}$ from Figure 5 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 of $G_{\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 $\operatorname{val}_{M}(a)=\textup{{True}}$ to the
output pair $\\{c_{1},c_{2}\\}$ via additional one-way switches $O^{k}_{ca}$,
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 color multiplicity at most $4$, the
resulting graph $G_{M}$ also has color multiplicity at most $4$. Moreover, the
graph $G_{M}$ can be constructed in AC0 because we only need to replace every
node and edge of $M$ by a gadget of bounded size that only depends on whether
the node is an input node, an $\and$-node or an $\mathrm{OR}$-node.

Recall that $G_{M}$ contains, for every node $a$ of $M$, a vertex pair
$\\{a_{1},a_{2}\\}$. We first prove that the vertex pairs of all nodes
evaluating to False are indeed split by $k$-$\mathrm{WL}$.

######  Lemma 4.7 (compare [19, Section 5.4], [2, Proof of Theorem 7.11]).

For every monotone circuit $M$ with output node $c$, and every node $a$ of
$M$, if either $\operatorname{val}_{M}(a)=\textup{{False}}$ or
$\operatorname{val}_{M}(c)=\textup{{False}}$, then
$(G_{M},a_{1})\not\equiv_{k\text{-}\mathrm{WL}}(G_{M},a_{2})$

######  Proof 4.8.

We split the proof into two claims.

######  Claim 7.

If $\operatorname{val}_{M}(a)=\textup{{False}}$, then
$(G_{M},a_{1})\not\equiv_{k\text{-}\mathrm{WL}}(G_{M},a_{2})$. We argue by
induction on the depth of $a$ in the circuit $M$. If $a$ is an input node,
then $a_{1}$ and $a_{2}$ have different colors and are thus distinguished by
construction. Thus, assume that $a$ is an inner node with parents $b$ and
$b^{\prime}$ and assume by induction that the claim is true for both $b$ and
$b^{\prime}$.

If $a$ is an $\and$-node, assume w.l.o.g. that
$\operatorname{val}_{M}(b)=\textup{{False}}$. By the induction hypothesis,
$(G_{M},b_{1})\not\equiv_{k\text{-}\mathrm{WL}}(G_{M},b_{2})$. But this means
that the input pair of the one-way switch $O^{k}_{ba}$ is split, which implies
that also the output pair is split. But this output pair is one of the input
pairs of the $\and$-gadget $G_{\and}$, whose output pair is
$\\{a_{1},a_{2}\\}$. Thus, $k\text{-}\mathrm{WL}$ also splits the pair
$\\{a_{1},a_{2}\\}$.

If $a$ is an $\mathrm{OR}$-node, then
$\operatorname{val}_{M}(b)=\operatorname{val}_{M}(b^{\prime})=\textup{{False}}$.
Thus, by the induction hypothesis, both of the pairs $\\{b_{1},b_{2}\\}$ and
$\\{b_{1}^{\prime},b_{2}^{\prime}\\}$ are split by $k\text{-}\mathrm{WL}$.
Using the one-way switches $O^{k}_{ba}$ and $O^{k}_{b^{\prime}a}$, this means
that $k\text{-}\mathrm{WL}$ also splits both input pairs of the
$\mathrm{OR}$-gadget $G_{\mathrm{OR}}$ whose output pair is
$\\{a_{1},a_{2}\\}$. However, all inner vertices of the gadget
$G_{\mathrm{OR}}$ are uniquely determined by their neighborhood among the
input pairs, and the two vertices of the output pair have distinct
neighborhoods among these inner vertices. Thus, $k\text{-}\mathrm{WL}$ also
splits the pair $\\{a_{1},a_{2}\\}$.

######  Claim 8.

If $\operatorname{val}_{M}(c)=\textup{{False}}$, then for all nodes $a$ of $M$
it holds that $(G_{M},a_{1})\not\equiv_{k\text{-}\mathrm{WL}}(G_{M},a_{2})$.
Using the previous claim, we get that $k$-$\mathrm{WL}$ splits the pair
$\\{c_{1},c_{2}\\}$. Using the one-way switches $O^{k}_{ca}$ connecting the
pair $\\{c_{1},c_{2}\\}$ to all pairs $\\{a_{1},a_{2}\\}$ corresponding to
input nodes of value True, this means that $k$-$\mathrm{WL}$ now splits all
pairs corresponding to input nodes. Thus, the graph now simulates the circuit
with all input nodes set to False. But as the circuit is monotone, this means
that also all inner nodes now evaluate to False. By the previous claim,
$k$-$\mathrm{WL}$ thus also splits all pairs $\\{a_{1},a_{2}\\}$ corresponding
to inner nodes.

Combining the two claims finishes the proof.

Next, we prove the converse: Nodes of value True get interpreted as vertex
pairs which are not split by $k\text{-}\mathrm{WL}$.

######  Lemma 4.9 (compare [19, Section 5.4], [2, Proof of Theorem 7.11]).

For every monotone circuit $M$ with output node $c$, and every node $a\in
V(M)$, if $\operatorname{val}_{M}(a)=\textup{{True}}$ and
$\operatorname{val}_{M}(c)=\textup{{True}}$, then
$(G_{M},a_{1})\equiv_{k\text{-}\mathrm{WL}}(G_{M},a_{2})$.

######  Proof 4.10.

To prove the desired equivalences, we provide winning strategies for
Duplicator in the bijective $(k+1)$-pebble game on $G_{M}$. We call a vertex
pair $\\{v_{1},v_{2}\\}$ in $G_{M}$ _true_ if it either corresponds to a node
$v$ of $M$ with $\operatorname{val}_{M}(v)=\textup{{True}}$, or is the output
pair of a one-way switch whose input pair corresponds to a node of value True.
Otherwise, we call $\\{v_{1},v_{2}\\}$ _false_. We call a one-way switch in
$G_{M}$ _true_ if its input pair is a true pair, and _false_ if its input pair
is a false pair.

Now, we call a position $P$ in the bijective $k+1$-pebble game on $G_{M}$
_safe_ , if there is an automorphism $\varphi$ of the subgraph induced by all
vertices of $G_{M}$ besides the inner vertices of one-way switches satisfying
the following conditions:

  1. 1.

The position $P\cup\varphi$, that is, the position obtained from $P$ by adding
all pebble pairs $x\mapsto\varphi(x)$ for $x\in\operatorname{dom}(\varphi)$,
is a partial isomorphism.

  2. 2.

For every false one-way switch $O$, $\varphi$ fixes both input and both output
vertices of $O$, and the restriction $P|_{O}$ of the position $P$ to vertices
of $O$ is the identity map.

  3. 3.

One of the following is true:

    1. (a)

There is a single true one-way switch $O$ with output pair $\\{x_{1},x_{2}\\}$
that contains all $k+1$ pebble pairs, and either $P$ is trapped and $\varphi$
fixes both $x_{1}$ and $x_{2}$, or $P$ is twisted and $\varphi$ exchanges
$x_{1}$ and $x_{2}$.

    2. (b)

Every true one-way switch contains at most $k$ pebble pairs, and for every
true one-way switch $O$ with input pair $\\{y_{1},y_{2}\\}$ and output pair
$\\{x_{1},x_{2}\\}$, either $P|_{O}\cup\\{y_{1}\mapsto\varphi(y_{1})\\}$ is
trapped and $\varphi$ fixes both $x_{1}$ and $x_{2}$, or
$P|_{O}\cup\\{y_{1}\mapsto\varphi(y_{1})\\}$ is twisted and $\varphi$
exchanges $x_{1}$ and $x_{2}$.

We call a position _dangerous_ if it is not safe.

######  Claim 9.

For every node $a\in V(M)$ with $\operatorname{val}_{M}(a)=\textup{{True}}$,
the position $a_{1}\mapsto a_{2}$ is safe. Moreover, the witnessing
automorphism $\varphi$ can be chosen such that it is the identity on every
gadget but the gadget corresponding to the node $a$. Let $a$ be an arbitrary
node of $C$. If $a$ is an input node, let $\varphi$ be the map that exchanges
$a_{1}$ and $a_{2}$ and fixes every other vertex. This clearly satisfies
Conditions 1 and 2. Condition 3 is trivially true, because every color-
preserving permutation of the input- and output vertices of a one-way switch
is either twisted or trapped.

If $a$ is an $\and$-node, pick $\varphi$ to be the unique non-trivial
automorphism on the corresponding $\and$-gadget $G_{\and}$, and the identity
everywhere else. Again, all three conditions are clearly satisfied in this
case because both parents of $a$ also have value True. If $a$ is an
$\mathrm{OR}$-node, let $b$ be a parent node of $a$ with
$\operatorname{val}_{M}(b)=\textup{{True}}$, and let $\varphi$ be the unique
automorphism that exchanges $a_{1}$ and $a_{2}$, as well as $b_{1}$ and
$b_{2}$ on the corresponding $\mathrm{OR}$-gadget $G_{\mathrm{OR}}$, and that
is the identity everywhere else. Again, all three conditions are clear by
construction.

######  Claim 10.

Every subposition of a safe position $P$ is safe. Assume $P$ is a safe
position and let $\varphi$ be the automorphism from the definition of safeness
for $P$.

If $P$ satisfies Condition 3b, then $\varphi$ also witnesses that every
subposition of $P$ is safe. Indeed, because subpositions of partial
isomorphisms are again partial isomorphisms, Condition 1 is clear. Similarly,
Condition 2 is true because restrictions of the identity are again the
identity on the restricted domain. Condition 3b follows from the observation
that every subposition of a trapped position is trapped, and every subposition
of a twisted position is twisted.

If $P$ satisfies Condition 3a instead, then no proper subposition of $P$ does
also satisfy Condition 3a. Let $O$ be the unique true one-way switch that
contains all $k+1$ pebble pairs, and let $P_{0}\subsetneq P$ be a proper
subposition. By Condition 3a of $P$, the position $P$ and thus also $P_{0}$ is
either trapped or twisted. In order to prove Condition 3b for the position
$P_{0}$, we need to show that we can extend this trapped or twisted position
by the vertex $y_{1}$. For this, consider the bijective $(k+1)$-pebble game in
position $P_{0}$ on $O$. Assume Spoiler picks up an unused pebble pair, and
let $\psi\colon V(O)\to V(O)$ be the bijection that Duplicator responds with
when following a trapped or twisted strategy. Then the position
$P_{0}\cup\\{y_{1}\mapsto\psi(y_{1})\\}$ is again trapped or twisted. Thus, in
order to ensure Condition 3b for $P_{0}$, it remains to construct the
automorphism $\varphi_{0}$ for $P_{0}$ such that
$\varphi_{0}(y_{1})=\psi(y_{1})$.

To construct this automorphism, we start with the automorphism $\varphi$ that
witnessed safeness of $P$. The position $P_{0}$ together with $\varphi$
satisfies Condition 1. If $\varphi(y_{1})=\psi(y_{1})$, we are thus done.
Hence, assume from now on that $\varphi(y_{1})\neq\psi(y_{1})$. Because the
input pair $\\{y_{1},y_{2}\\}$ corresponds to a node of value True, Claim 9
gives us a second automorphism $\theta_{y}$ which exchanges $y_{1}$ and
$y_{2}$, and is the identity on every gadget besides the input-, $\and$\- or
$\mathrm{OR}$-gadget containing $y_{1}$ and $y_{2}$. We set
$\varphi_{0}\coloneqq\theta_{y}\circ\varphi$. Then $\varphi_{0}$ is an
automorphism satisfying $\varphi_{0}(y_{1})=\psi(y_{1})$, which furthermore
agrees with $\varphi$ everywhere but on the gadget containing $y_{1}$ and
$y_{2}$. Moreover, by Condition 2 applied to the position $y_{1}\mapsto y_{2}$
and $\theta$, the automorphism $\varphi_{0}$ disagrees with $\varphi$ only on
$y_{1}$ and $y_{2}$, where $P_{0}\cup\varphi_{0}$ is a partial isomorphism by
construction, and possibly on output pairs of one-way switches whose input
pairs correspond to a node of value True. But for these one-way switches, we
can independently exchange or fix the two vertices of the input and the output
pair while keeping the resulting position either trapped or twisted. This
proves Conditions 1 and 2.

######  Claim 11.

Duplicator can avoid dangerous positions from safes ones in the bijective
$(k+1)$-pebble game on $G_{M}$. Let $P$ be a safe position and $\varphi$ the
witnessing automorphism. As subpositions of safe positions are again safe, it
suffices to assume that $P$ contains at most $k$ of the possible $k+1$ pebble
pairs. Now, if a single true one-way switch $O$ contains all $k$ pebbles, then
the position $P=P|_{O}$ is trapped or twisted, and Duplicator picks a
bijection $\psi|_{O}$ according to a trapped or twisted strategy.

If $\psi|_{O}$ and $\varphi$ agree on the input pair $\\{y_{1},y_{2}\\}$ of
$O$, then $\psi|_{O}$ is compatible with $\varphi$. Otherwise, we again pick
the automorphism $\theta_{y}$ that Claim 9 yields for the position
$y_{1}\mapsto y_{2}$ and replace $\varphi$ by $\theta_{y}\circ\varphi$, which
is now compatible with $\psi|_{O}$.

As all other one-way switches $O^{\prime}$ do not contain any pebble pairs on
inner vertices, and the position $P$ is safe, the restrictions
$\varphi|_{O^{\prime}}$ are the identity on all false one-way switches, and
either trapped or twisted on all true one-way switches. We choose
$\psi|_{O^{\prime}}$ according to a trapped, twisted or identity strategy on
these one-way switches. Combining the maps $\psi|_{O^{\prime}}$ for all one-
way switches with $\varphi$ yields a total bijection $\psi$, which Duplicator
can choose.

Now, if Spoiler places the free pebbles on vertices $x$ and $\psi(x)$, we need
to argue that the resulting position is still safe. However, Condition 1 is
true because $\psi$ was chosen according to a winning strategy on each gadget,
and these strategies are compatible at the intersections of the gadgets.
Conditions 2 and 3 are true by construction. Thus, the position
$P\cup\\{x\mapsto\psi(x)\\}$ is again safe.

Assume now that every true one-way switch of $G_{M}$ contains at most $k-1$
pebble pairs of $P$, and let $\varphi$ be the map which witnesses that $P$ is
safe. Then, Condition 3b guarantees that for all one-way switches $O$ with
input pair $\\{y_{1},y_{2}\\}$ and output pair $\\{x_{1},x_{2}\\}$, we can
pick the bijection $\psi|_{O}$ according to a trapped, twisted or identity
strategy on
$P|_{O}\cup\\{x_{1}\mapsto\varphi(x_{1}),y_{1}\mapsto\varphi(y_{1})\\}$. This
ensures that $\psi|_{O}$ is compatible with $\varphi$, which means that we get
a total bijection $\psi$, which Duplicator chooses. Again, each of the
positions $P\cup\\{x\mapsto\psi(x)\\}$ is again safe by construction.

Thus, for every node $a$ with $\operatorname{val}_{M}(a)=\textup{{True}}$,
Duplicator has a winning strategy in position $a_{1}\mapsto a_{2}$ by always
staying in safe positions. This proves
$(G_{M},a_{1})\equiv_{k\text{-}\mathrm{WL}}(G_{M},a_{2})$.

Similar to [19], combining Lemma 4.7 with Lemma 4.9 yields:

######  Corollary 4.11.

The $k$-$\mathrm{WL}$-equivalence problem for vertices is P-hard under uniform
AC0-reductions, both over colored simple graphs of color multiplicity $4$, and
over uncolored simple graphs.

######  Proof 4.12.

The claim for colored simple graphs of color multiplicity $4$ follows from
P-hardness of the monotone circuit value problem, the observation that the
graph $G_{M}$ can be constructed in AC0 together with Lemma 4.7 and Lemma 4.7.

To show P-hardness of the $k$-$\mathrm{WL}$-equivalence problem over uncolored
simple graphs, we need to eliminate the vertex-colors without affecting the
$k$-$\mathrm{WL}$-color partition on the original graph. To do this let
$\chi\colon G_{M}\to C$ be the vertex-coloring of $G_{M}$, where $C$ is a set
of colors of polynomial size. Assume w.l.o.g. that $\chi$ is surjective, i.e.
all colors in $C$ are used.

We construct an uncolored simple graph $G_{M}^{C}$ from $G_{M}$ as follows: we
start by adding to $G_{M}$ a fresh universal vertex $u$. Then, we add a path
$P$ to $G_{M}$ with vertex set $C$, and further add a fresh vertex $v_{0}$ to
one end of the path. Finally, we connect each vertex $x\in V(G_{M})$ to the
vertex $\chi(x)\in C$. This finishes the construction of $G_{M}^{C}$. This
construction can be carried out in AC0: the path $P$ is independent of the
input and can hence just be hardcoded into the circuit, and the additional
edges only depend on the vertex-color.

Next, we argue that replacing the colored graph $G_{M}$ by the uncolored graph
$G_{M}^{C}$ does not affect the power of the Weisfeiler-Leman algorithm. For
this, note that the universal vertex $u$ is the unique vertex in $G_{M}^{C}$
of maximal degree, and hence distinguished even by color refinement. Thus, its
neighborhood, which is the vertex set of $G_{M}\subseteq G_{M}^{C}$ is also
distinguished from its non-neighborhood, which is the path $P$. The path $P$
contains a single vertex of degree $1$, namely the vertex $v_{0}$ we added to
one end, which means that color refinement completely discretizes $P$. But
because the color classes of $G_{M}\subseteq G_{M}^{C}$ are precisely the
neighborhoods of the vertices on $P$ in $G_{M}$, color refinement recomputes
the color partition induced on $G_{M}$ by $\chi$, while discretizing every
vertex we added. The claim now follows from the observation that adding
discrete vertices which are homogeneously connected to every color class does
not affect the power of the Weisfeiler-Leman algorithm.

Thus, Lemma 4.7 and Lemma 4.9 are also true for the graph $G_{M}^{C}$, which
proves P-hardness of the $k$-$\mathrm{WL}$-identification problem for
uncolored simple graphs.

In order to further reduce to the identification problem, we need to consider
identification of the graph $G_{M}$.

######  Lemma 4.13.

Let $M$ be a monotone circuit with output node $c$ which evaluates to False.
Then $G_{M}$ is identified by $k$-$\mathrm{WL}$.

######  Proof 4.14.

By Lemma 4.7, all pairs $\\{a_{1},a_{2}\\}$ corresponding to a node $a\in
V(M)$ are split by $k$-$\mathrm{WL}$. Translating these splits through the
one-way switches, this implies that everything in $G_{M}$ besides the one-way
switches is discretized by $k$-$\mathrm{WL}$. But as this includes all input
and output pairs of the one-way switches, the fact that the graphs
$O^{k}_{{\mathrm{split}}}$ are identified implies that all one-way switches
are identified as subgraphs of $G_{M}$.

All individual parts of the graph $G_{M}$ are thus identified as subgraphs of
$G_{M}$. As moreover all edges are contained in one fo the individual parts,
and different parts only overlap in input and output pairs, all of which are
discretized by $k$-$\mathrm{WL}$, it follows that the whole graph $G_{M}$ is
identified by $k$-$\mathrm{WL}$.

Consider now the modified graph $G^{*}_{M}$ we get by adding another freshly
colored one-way switch $O^{k}_{*}$ to $G_{M}$ whose input pair is
$\\{c_{1},c_{2}\\}$, i.e., the vertex pair corresponding to the output node of
the circuit $M$. Additionally, we color one of the output vertices of
$O^{k}_{*}$ in another color.

######  Lemma 4.15.

The following are equivalent:

  1. (i)

$\operatorname{val}_{M}(c)=\textup{{False}}$,

  2. (ii)

$(G_{M},c_{1})\not\equiv_{k\text{-}\mathrm{WL}}(G_{M},c_{2})$ and

  3. (iii)

$G^{*}_{M}$ is identified by $k$-$\mathrm{WL}$.

######  Proof 4.16.

The equivalence of Conditions 1 and 2 follows from Lemma 4.7 and Lemma 4.9. We
show that Condition 2 implies Condition 3. Assume that
$(G_{M},c_{1})\not\equiv_{k\text{-}\mathrm{WL}}(G_{M},c_{2})$. This splits the
input pair of $O^{k}_{*}$. Using the properties of the one-way switch, this
also splits the output pair of $O^{k}_{*}$ and $O^{k}_{*}$ is now identified
as a subgraph of $G^{*}_{M}$. As $G_{M}$ is also identified by Lemma 4.13 and
both parts interact only at the split pair $\\{c_{1},c_{2}\\}$, the whole
graph $G^{*}_{M}$ is identified.

We finally show that Condition 3 implies Condition 2 by contraposition. Assume
$(G_{M},c_{1})\equiv_{k\text{-}\mathrm{WL}}(G_{M},c_{2})$, and consider the
graph $(G^{*}_{M})^{\prime}$ we obtain by following the same construction as
for $G^{*}_{M}$, but then coloring the other output vertex of $O^{k}_{*}$.
These two graphs are non-isomorphic, as the two output vertices of our one-way
switches do not lie in the same orbit. They are, however, equivalent under
$k\text{-}\mathrm{WL}$: Duplicator can follow a twisted strategy to win
between the two one-way switches and use an arbitrary winning strategy on
$G_{M}$. If none of the two parts contains all pebble pairs, these two
strategies can be made compatible at the pair $\\{c_{1},c_{2}\\}$ by enforcing
which of the two maps $c_{1}\mapsto c_{1}$ or $c_{1}\mapsto c_{2}$ both
strategies should be compatible with. If all pebble pairs lie in one of the
two parts, Duplicator can choose their strategy on this part first and then
extend it to a winning strategy on the whole graph by using that
$(G_{M},c_{1})\equiv_{k\text{-}\mathrm{WL}}(G_{M},c_{2})$. This proves that
$G^{*}_{M}\equiv_{k\text{-}\mathrm{WL}}(G^{*}_{M})^{\prime}$ and thus that
$G^{*}_{M}$ is not identified by $k$-$\mathrm{WL}$.

This finally yields our hardness result. *

######  Proof 4.17.

P-hardness of the identification problem for graphs of color multiplicity $4$
follows from Lemma 4.15 and the hardness of the monotone circuit value
problem. Hardness for the class of simple graphs follows from the procedure
for the elimination of vertex colors which we already used in the proof of
Corollary 4.11.

##  5 Approximation of the Weisfeiler-Leman dimension for structures with
bounded abelian color classes

The approach we used in Section 3 to decide the
$k$-$\mathrm{WL}$-identification problem for graphs of color multiplicity at
most $5$ does not easily generalize to larger color multiplicity or to
relational structures of higher arity. In particular, Lemma 3.14, which was
crucial in the reduction of $k$-$\mathrm{WL}$-identification to a group-
theoretic problem, was based on an explicit case distinction on the possible
isomorphism types of interspaces, and fails for graphs of larger color
multiplicity. In this section, we consider the special case of relational
structures with abelian color classes, i.e., structures for which the
automorphism group of the structure induced on each color class is abelian.
Such structures were already considered in the context of descriptive
complexity theory [42] and include both CFI-graphs [11] and multipedes [36,
35] on ordered base graphs. We prove that for every fixed dimension $k$ and
color multiplicity $c$, there is a polynomial-time algorithm that
approximately solves the $k\text{-}\mathrm{WL}$-identification problem on
relational structures with abelian color classes of size at most $c$ in the
following sense: for every such structure $\mathfrak{A}$, the algorithm either
reports that $\mathfrak{A}$ is not identified by $k$-$\mathrm{WL}$, or that it
is identified by $(k+1)c\text{-}\mathrm{WL}$. In the former case, the
algorithm can witness non-identification by providing a second, non-isomorphic
but $k$-$\mathrm{WL}$-equivalent structure. The running time of our algorithm
is fixed-parameter tractable in $c$, but only slice-wise polynomial in $k$.

We achieve this by only considering those algebraic isomorphisms that are at
least locally induced by a combinatorial isomorphism. This will allow us to
adapt the group-theoretic techniques from Section 3.3. In this whole section,
we fix a dimension $k\geq 2$ and a number $\ell\geq k+1$.

###  5.1 Local vs. algebraic isomorphisms

For a $k$-ary coherent configuration $\mathcal{C}$ and a set of fibers
${{\mathbf{X}}}\subseteq F(\mathcal{C})$, we also write
$\mathcal{C}[{{\mathbf{X}}}]$ for
$\mathcal{C}\left[\bigcup{{\mathbf{X}}}\right]$. An _$\ell$ -local
isomorphism_ between $k$-ary coherent configurations $\mathcal{C}$ and
$\mathcal{D}$ is a family
$(\varphi_{{\mathbf{X}}})_{{{\mathbf{X}}}\in\binom{F(\mathcal{C})}{\ell}}$ of
combinatorial isomorphisms such that there exists a bijection $\beta\colon
F(\mathcal{C})\to F(\mathcal{D})$ satisfying the following conditions:

(LI1)

For all ${{\mathbf{X}}}\in\binom{F(\mathcal{C})}{\ell}$, the map
$\varphi_{{\mathbf{X}}}$ is a combinatorial isomorphism between the $k$-ary
coherent configurations $\mathcal{C}[{{\mathbf{X}}}]$ and
$\mathcal{D}[\beta({{\mathbf{X}}})]$.

(LI2)

For all ${{\mathbf{Y}}},{{\mathbf{Z}}}\in\binom{F(\mathcal{C})}{\ell}$, the
algebraic actions of $\varphi_{{\mathbf{Y}}}$ and $\varphi_{{\mathbf{Z}}}$
agree on $\mathcal{C}[{{\mathbf{Y}}}\cap{{\mathbf{Z}}}]$, i.e., for all basis
relations $R\in\mathcal{C}[{{\mathbf{Y}}}\cap{{\mathbf{Z}}}]$ we have
$\varphi_{{\mathbf{Y}}}(R)=\varphi_{{\mathbf{Z}}}(R)$.

Condition (LI2) ensures that every $\ell$-local isomorphism induces a
bijection on the set of basis relations. When $\mathcal{C}$ and $\ell$ are
clear from context, we write $(\varphi_{{\mathbf{X}}})_{{\mathbf{X}}}$ instead
of $(\varphi_{{\mathbf{X}}})_{{{\mathbf{X}}}\in\binom{F(\mathcal{C})}{\ell}}$.

We say that an $\ell$-local isomorphism
$(\varphi_{{\mathbf{X}}})_{{{\mathbf{X}}}}$ between $k$-ary coherent
configurations $\mathcal{C}$ and $\mathcal{D}$ is induced by a combinatorial
isomorphism $\hat{\varphi}$ if $\hat{\varphi}$ and
$(\varphi_{{\mathbf{X}}})_{{{\mathbf{X}}}}$ induce the same algebraic action
on all basis relations of $\mathcal{C}$. A $k$-ary coherent configuration
$\mathcal{C}$ is _$\ell$ -locally determined_ if every $\ell$-local
isomorphism
$(\varphi_{{\mathbf{X}}})_{{{\mathbf{X}}}}\colon\mathcal{C}\to\mathcal{D}$ is
induced by a combinatorial isomorphism.

######  Lemma 5.1.

Let $\mathcal{C}$ and $\mathcal{D}$ be $k$-ary coherent configurations of
color multiplicity $c$.

  1. 1.

Every $(k+1)$-local isomorphism between $\mathcal{C}$ and $\mathcal{D}$
induces an algebraic isomorphism.

  2. 2.

For every algebraic isomorphism
$f\colon\operatorname{WL}_{(k+1)c}(\mathcal{C})\to\operatorname{WL}_{(k+1)c}(\mathcal{D})$,
the map $f|_{k}\colon\mathcal{C}\to\mathcal{D}$ is induced by a $(k+1)$-local
isomorphism.

In particular:

  1. 3.

If $\mathcal{C}$ is separable, then $\mathcal{C}$ is ($k+1$)-locally
determined.

  2. 4.

If $\mathcal{C}$ is ($k+1$)-locally determined, then
$\operatorname{WL}_{(k+1)c}(\mathcal{C})$ is separable.

######  Proof 5.2.

For the first claim, let
$(\varphi_{{\mathbf{X}}})_{{{\mathbf{X}}}\in\binom{F(\mathcal{C})}{k+1}}\colon\mathcal{C}\to\mathcal{D}$
be a $(k+1)$-local isomorphism and let $f_{\varphi}$ be the induced algebraic
map on the basis relations. On every choice of $k+1$ fibers ${{\mathbf{X}}}$,
$f_{\varphi}|_{\mathcal{C}[{{\mathbf{X}}}]}$ is induced by the combinatorial
isomorphism $\varphi_{{\mathbf{X}}}$.

A map $f\colon\mathcal{C}\to\mathcal{D}$ compatible with faces is an algebraic
isomorphism if and only if
$f|_{{\mathbf{X}}}\colon\mathcal{C}[{\mathbf{X}}]\to\mathcal{D}[f({\mathbf{X}})]$
is an algebraic isomorphism for every set of $k+1$ fibers ${\mathbf{X}}$. This
is because an intersection number $p\left(R;R_{1},\dots,R_{k}\right)$ can only
be non-zero if the one-dimensional faces of $R$ and $R_{i}$ agree in all but
the $i$-th component, and the $i$-th faces of $R_{i}$ all agree. Thus, the
basis relations $R,R_{1},\dots,R_{k}$ must all be contained in some
subconfiguration $\mathcal{C}[{{\mathbf{X}}}]$ on $k+1$ fibers
${{\mathbf{X}}}$. Because the map $f_{\varphi}$ is induced by a combinatorial
isomorphism on every union of at most $k+1$ fibers, it is hence an algebraic
isomorphism there and thus everywhere.

For the second claim, pick a set of $k+1$ fibers
${{\mathbf{X}}}\in\binom{F(\mathcal{C})}{k+1}$. Then

$f|_{{\mathbf{X}}}\colon\operatorname{WL}_{(k+1)c}(\mathcal{C})[{{\mathbf{X}}}]\to\operatorname{WL}_{(k+1)c}(\mathcal{D})[f({{\mathbf{X}}})]$

is an algebraic isomorphism between $(k+1)c$-ary coherent configurations of
order at most $(k+1)c$. Thus, $f|_{{\mathbf{X}}}$ is induced by a
combinatorial isomorphism $\varphi_{{\mathbf{X}}}$ for every set of fibers
${{\mathbf{X}}}\in\binom{F(\mathcal{C})}{k+1}$. Combining these local
combinatorial isomorphisms yields a $(k+1)$-local isomorphism inducing
$f|_{k}$.

For a relational structure $\mathfrak{A}$ and
$\mathcal{C}=\operatorname{WL}_{k}(\mathfrak{A})$, Lemma 5.1 implies the
following:

######  Corollary 5.3.

Let $\mathfrak{A}$ be a $k$-ary relational structure of color multiplicity
$c$.

  1. 1.

If $\operatorname{WL}_{k}(\mathfrak{A})$ is ($k+1$)-locally determined, then
$\operatorname{WL-dim}(\mathfrak{A})\leq(k+1)c$.

  2. 2.

If $\operatorname{WL}_{k}(\mathfrak{A})$ is not ($k+1$)-locally determined,
then $\operatorname{WL-dim}(\mathfrak{A})>k$.

Thus, deciding whether the $k$-ary coherent configuration
$\operatorname{WL}_{k}(\mathfrak{A})$ is ($k+1$)-locally determined yields an
approximation of the Weisfeiler-Leman dimension of $\mathfrak{A}$.

###  5.2 Deciding $\ell$-local determination

We now show that it is polynomial-time decidable whether a $k$-ary coherent
configuration with bounded abelian fibers (a formal definition will follow) is
$\ell$-locally determined. For this, we adapt the techniques developed in
Section 3.3. Recall that a coherent configuration of color multiplicity $5$ is
separable if and only if every strict algebraic automorphism is induced by a
combinatorial one (Lemma 3.14). Towards characterizing $\ell$-local
determination in a similar way, we now introduce the corresponding notion of a
strict algebraic automorphism for $\ell$-local isomorphisms.

A combinatorial automorphism $\varphi$ of a $k$-ary coherent configuration
$\mathcal{D}$ is _color-preserving_ if $\varphi$ fixes every basis relation of
$\mathcal{D}$. This is equivalent to $\varphi$ being an automorphism of every
colored variant of $\mathcal{D}$ and to the algebraic automorphism induced by
$\varphi$ being the identity (recall that combinatorial automorphisms are not
required to fix every basis relation, but only the partition of
$V(\mathcal{D})^{k}$ into basis relations). We denote by
$\operatorname{Aut_{col}}(\mathcal{D})$ the group of color-preserving
combinatorial automorphisms of $\mathcal{D}$. We say that a coherent
configuration $\mathcal{C}$ has _abelian fibers_ if, for each fiber $X\in
F(\mathcal{C})$, the group $\operatorname{Aut_{col}}(\mathcal{C}[X])$ is
abelian.

A permutation $\pi$ of the vertex set $V(\mathcal{C})$ of a coherent
configuration $\mathcal{C}$ is _color-class-preserving_ if, for each fiber
$X\in F(\mathcal{C})$, the restriction $\pi|_{X}$ is a color-preserving
combinatorial automorphism of $\mathcal{C}[X]$. We write
$\mathbb{P}(\mathcal{C})$ for the group of all color-class-preserving
permutations of $\mathcal{C}$. It satisfies
$\mathbb{P}(\mathcal{C})=\prod_{X\in
F(\mathcal{C})}\operatorname{Aut_{col}}(\mathcal{C}[X])$.

An _$\ell$ -local permutation_ of a $k$-ary coherent configuration
$\mathcal{C}$ is an $\ell$-local isomorphism
$(\varphi_{{\mathbf{X}}})_{{\mathbf{X}}}$ from $\mathcal{C}$ to some
configuration $\mathcal{C^{\prime}}$ such that
$V(\mathcal{C})=V(\mathcal{C^{\prime}})$ and
$\varphi_{{\mathbf{X}}}\in\mathbb{P}(\mathcal{C}[{{\mathbf{X}}}])$ for all
${{\mathbf{X}}}\in\binom{F(\mathrm{C})}{\ell}$. In other words, it is a family
$(\varphi_{{\mathbf{X}}})_{{{\mathbf{X}}}\in\binom{F(\mathcal{C})}{\ell}}$ of
color-preserving combinatorial automorphisms
$\varphi_{{\mathbf{X}}}\in\mathbb{P}(\mathcal{C}[{{\mathbf{X}}}])$ on $\ell$
fibers with the property that for all
${{\mathbf{Y}}},{{\mathbf{Z}}}\in\binom{F(\mathcal{C})}{\ell}$, the maps
$\varphi_{{\mathbf{Y}}}$ and $\varphi_{{\mathbf{Z}}}$ induce the same
algebraic action on $\mathcal{C}[{{\mathbf{Y}}}\cap{{\mathbf{Z}}}]$. We write
$\mathbb{L}_{\ell}(\mathcal{C})$ for the set of all $\ell$-local permutations
of $\mathcal{C}$. Each element $\varphi\in\mathbb{L}_{\ell}(\mathcal{C})$
induces an algebraic isomorphism
$f_{\varphi}\colon\mathcal{C}\to\mathcal{C}^{\varphi}$ that fixes every basis
relation contained in a single fiber. We write
$\mathbb{C}_{\ell}(\mathcal{C})$ for the set of those $\ell$-local
permutations $\varphi$ for which $f_{\varphi}$ is induced by a combinatorial
isomorphism. In general, $\mathbb{L}_{\ell}(\mathcal{C})$ and
$\mathbb{C}_{\ell}(\mathcal{C})$ are no groups, but if $\mathcal{C}$ has
abelian fibers, then they are:

######  Lemma 5.4.

Let $\mathcal{C}$ be a $k$-ary coherent configuration with abelian fibers.
Then:

  1. 1.

$\mathbb{L}_{\ell}(\mathcal{C})$ forms a group under component-wise
composition, and

  2. 2.

$\mathbb{C}_{\ell}(\mathcal{C})$ forms a subgroup of
$\mathbb{L}_{\ell}(\mathcal{C})$.

######  Proof 5.5.

Clearly,
$(\operatorname{id}_{{\mathbf{X}}})_{{{\mathbf{X}}}\in\binom{F(\mathcal{C})}{\ell}}\in\mathbb{C}_{\ell}(\mathcal{C})\subseteq\mathbb{L}_{\ell}(\mathcal{C})$
is an identity element in both sets.

We first note that whenever $\varphi$ and $\psi$ are color-class-preserving
permutations of $V(\mathcal{C})$, then $\varphi\circ\psi=\psi\circ\varphi$.
This is because, on every fiber $X\in F(\mathcal{C})$, the restrictions
$\varphi|_{X}$ and $\varphi|_{Y}$ are both elements of the abelian group
$\operatorname{Aut_{col}}(\mathcal{C}[X])$.

Now, for two strict $\ell$-local permutations
$(\varphi_{{\mathbf{X}}})_{{{\mathbf{X}}}\in\binom{F(\mathcal{C})}{\ell}},(\psi_{{\mathbf{X}}})_{{{\mathbf{X}}}\in\binom{F(\mathcal{C})}{\ell}}\in\mathbb{L}_{\ell}(\mathcal{C})$
we need to show that also
$(\varphi_{{\mathbf{X}}}\circ\psi_{{\mathbf{X}}})_{{{\mathbf{X}}}\in\binom{F(\mathcal{C})}{\ell}}$
is a strict $\ell$-local automorphism. Let
${{\mathbf{Y}}},{{\mathbf{Z}}}\in\binom{F(\mathcal{C})}{\ell}$. Because
$\varphi_{{\mathbf{Y}}}$ and $\psi_{{\mathbf{Y}}}$ are both color-class-
preserving, their composition is, too. For an arbitrary basis relation
$R\in\mathcal{C}[{{\mathbf{Y}}}\cap{{\mathbf{Z}}}]$, we now get

$\displaystyle(\varphi_{{\mathbf{Y}}}\circ\psi_{{\mathbf{Y}}})(R)$
$\displaystyle=\varphi_{{\mathbf{Y}}}(\psi_{{\mathbf{Y}}}(R))=\varphi_{{\mathbf{Y}}}(\psi_{{\mathbf{Z}}}(R))=(\varphi_{{\mathbf{Y}}}\circ\psi_{{\mathbf{Z}}})(R)=(\psi_{{\mathbf{Z}}}\circ\varphi_{{\mathbf{Y}}})(R)$
(2)
$\displaystyle=\psi_{{\mathbf{Z}}}(\varphi_{{\mathbf{Y}}}(R))=\psi_{{\mathbf{Z}}}(\varphi_{{\mathbf{Z}}}(R))=(\psi_{{\mathbf{Z}}}\circ\varphi_{{\mathbf{Z}}})(R)=(\varphi_{{\mathbf{Z}}}\circ\psi_{{\mathbf{Z}}})(R).$

Next, we show that $\mathbb{L}_{\ell}(\mathcal{C})$ is closed under taking
inverses. For this, let
$(\varphi_{{\mathbf{X}}})_{{{\mathbf{X}}}\in\binom{F(\mathcal{C})}{\ell}}\in\mathbb{L}_{\ell}(\mathcal{C})$
and $R\in\mathcal{C}[{{\mathbf{Y}}}\cap{{\mathbf{Z}}}]$. Then

$\displaystyle\varphi_{{\mathbf{Y}}}^{-1}(R)$
$\displaystyle=(\varphi_{{\mathbf{Y}}}^{-1}\circ\varphi_{{\mathbf{Z}}}^{-1}\circ\varphi_{{\mathbf{Z}}})(R)=(\varphi_{{\mathbf{Y}}}^{-1}\circ\varphi_{{\mathbf{Z}}}^{-1})(\varphi_{{\mathbf{Z}}}(R))$
$\displaystyle=(\varphi_{{\mathbf{Y}}}^{-1}\circ\varphi_{{\mathbf{Z}}}^{-1})(\varphi_{{\mathbf{Y}}}(R))=(\varphi_{{\mathbf{Y}}}^{-1}\circ\varphi_{{\mathbf{Z}}}^{-1}\circ\varphi_{{\mathbf{Y}}})(R)=(\varphi_{{\mathbf{Z}}}^{-1})(R).$

Thus,
$(\varphi_{{\mathbf{X}}}^{-1})_{{{\mathbf{X}}}\in\binom{F(\mathcal{C})}{\ell}}\in\mathbb{L}_{\ell}(\mathcal{C})$.

To prove that $\mathbb{C}_{\ell}(\mathcal{C})$ is a subgroup of
$\mathbb{L}_{\ell}(\mathcal{C})$, we notice that a permutation $\theta$ of
$V(\mathcal{C})$ induces $(\varphi_{{\mathbf{X}}})_{{\mathbf{X}}}$ if and only
if
$\theta|_{{\mathbf{X}}}\circ\varphi_{{\mathbf{X}}}^{-1}\in\operatorname{Aut_{col}}(\mathcal{C}[{{\mathbf{X}}}])$
for all ${{\mathbf{X}}}\in\binom{F(\mathcal{C})}{\ell}$. Because the group
$\operatorname{Aut_{col}}(\mathcal{C}[{{\mathbf{X}}}])$ is abelian, this
condition is compatible with composition and taking inverses: if a
combinatorial isomorphism $\hat{\varphi}$ of $\mathcal{C}$ induces
$(\varphi_{{\mathbf{X}}})_{{{\mathbf{X}}}\in\binom{F(\mathcal{C})}{\ell}}$ and
another one $\hat{\psi}$ induces
$(\psi_{{\mathbf{X}}})_{{{\mathbf{X}}}\in\binom{F(\mathcal{C})}{\ell}}$, then
$\hat{\varphi}\circ\hat{\psi}$ induces
$(\varphi_{{\mathbf{X}}}\circ\psi_{{\mathbf{X}}})_{{{\mathbf{X}}}\in\binom{F(\mathcal{C})}{\ell}}$
and $\hat{\varphi}^{-1}$ induces
$(\varphi_{{\mathbf{X}}}^{-1})_{{{\mathbf{X}}}\in\binom{F(\mathcal{C})}{\ell}}$.

We are now ready to show that $\ell$-local determination is equivalent to
every $\ell$-local permutation being induced by a combinatorial isomorphism.

######  Lemma 5.6.

Let $\mathcal{C}$ be a $k$-ary coherent configuration with abelian fibers.
Then the following are equivalent:

  1. (i)

$\mathcal{C}$ is $\ell$-locally determined,

  2. (ii)

$\mathbb{L}_{\ell}(\mathcal{C})=\mathbb{C}_{\ell}(\mathcal{C})$.

######  Proof 5.7.

Assume that $\mathcal{C}$ is $\ell$-locally determined and pick an
$\ell$-local permutation
$(\varphi_{{\mathbf{X}}})_{{\mathbf{X}}}\in\mathbb{L}_{\ell}(\mathcal{C})$. We
define a new $k$-ary coherent configuration
$\mathcal{C}^{(\varphi_{{\mathbf{X}}})_{{\mathbf{X}}}}$ by pushing the
structure of $\mathcal{C}$ through ${(\varphi_{{\mathbf{X}}})_{{\mathbf{X}}}}$
in such a way that ${(\varphi_{{\mathbf{X}}})_{{\mathbf{X}}}}$ becomes a
$\ell$-local isomorphism from $\mathcal{C}$ to