and $r$ are identity maps, since the output signature of $\phi^{\prime}$
agrees with the output signature of $\phi$.

Since a Datalog∪ reduction is defined as a composition of a Datalog
interpretation with a union gadget, Theorem 3.13 is a direct corollary of
Lemma A.7.

###  A.2. Gadget reductions are Datalog∪ reductions

The goal of this subsection is to prove Theorem 3.12 which claims that every
gadget replacement is also expressible as a Datalog interpretation. We
decompose a gadget reduction as a composition of the reification and a
projective gadget using Lemma A.5. Since reification is a Datalog
interpretation, and Datalog reductions compose, it is enough to prove the
theorem for projective gadgets. For the rest of this subsection, we assume
that $\gamma$ is a projective gadget mapping $\Pi$-structures to
$\Sigma$-structures.

The first step is to prove that a Datalog program can ‘emulate’ a single
relation in the $\gamma$-image in the sense of the following lemma. To
simplify the statement, we assume that $\mathbf{D}_{t}^{\gamma}$’s are
disjoint and denote by $\mathbf{D}^{\gamma}$ the (disjoint) union of
$\mathbf{D}_{t}^{\gamma}$’s where $t$ ranges through $\Pi$-types.

######  Lemma A.10.

For each $\Sigma$-symbol $R$ of arity $k$, and each $k$-tuple
$g\in(\mathbf{D}^{\gamma})^{k}$, there is a Datalog program $\phi_{R,g}$ such
that: For every $\Pi$-structure $\mathbf{A}$ and every tuple $a\in A^{k}$,
$a\in\phi_{R,g}(\mathbf{A})$ if and only if
$([a_{1};g_{1}],\dots,[a_{k};g_{k}])\in R^{\gamma(\mathbf{A})}$.

In the statement above, we implicitly assume that, for each $i\in[k]$, the
$\Sigma$-type of $g_{i}$ is $\operatorname{ar}_{R}(i)$ and that the $\Pi$-type
type $t_{i}$ of $a_{i}$ is $t_{i}$ satisfies
$g_{i}\in\mathbf{D}_{t_{i}}^{\gamma}$. Consequently, the arity of the program
$\phi_{R,g}$ is $(t_{1},\dots,t_{k})$.

######  Proof A.11.

We construct the program $\phi_{R,g}$ with the required properties. In
addition to all $\Pi$-symbols which are EDBs, $\phi_{R,g}$ has a binary IDB
$I_{h_{1},h_{2}}$ for each $(h_{1},h_{2})\in\mathbf{D}^{\gamma}$, and an IDB
$R_{g}$ of arity $k$, and $\operatorname{ar}_{R}(i)=t_{i}$ for all $i$, which
is designated as output. Now, let us describe the rules of $\phi^{g}$.

  1. (1)

For every $\Pi$-symbol $S$ and
$h\in\mathbf{D}_{\operatorname{ar}_{2}(S)}^{\gamma}$, include the rule:

$I_{p_{S}(h),h}(x,y)\leftarrow S(x,y)$

  2. (2)

Include the rules:

$\displaystyle I_{h_{1},h_{1}}(x,x)$ $\displaystyle\leftarrow x=x$
$\displaystyle I_{h_{1},h_{2}}(x,y)$ $\displaystyle\leftarrow
I_{h_{2},h_{1}}(y,x)$ $\displaystyle I_{h_{1},h_{3}}(x,z)$
$\displaystyle\leftarrow I_{h_{1},h_{2}}(x,y),I_{h_{2},h_{3}}(y,z)$

for all $h_{1},h_{2},h_{3}\in\mathbf{D}^{\gamma}$.

  3. (3)

Finally, add the rule:

$R_{g}(x_{1},\dots,x_{k})\leftarrow
I_{g_{1},h_{1}}(x_{1},y),\dots,I_{g_{k},h_{k}}(x_{k},y)$

for each $h\in R^{\mathbf{D}^{\gamma}}$.

Let us show that $\phi_{R,g}$ has the required property. We start by observing
that a relation $I_{h_{1},h_{2}}(x,y)$ is derived in $\mathbf{A}$ if and only
if $[x;h_{1}]=[y;h_{2}]$—which follows since rules in item (1) introduce into
$I$ the equality constraints of the gadget, and rules in item (2) compute the
transitive symmetric reflexive closure of $I$. Observing this, it is
straightforward to see that

$([a_{1};g_{1}],\dots,[a_{k};g_{k}])\in R^{\gamma(\mathbf{A})}$

if and only if there exist a $\Pi$-type $s$, $b\in A_{s}$, and $h\in
R^{\mathbf{G}_{s}}$ such that $[b;h_{i}]=[a_{i};g_{i}]$ for all $i\in[k]$,
which is equivalent to triggering the rule (3).

######  Example A.12.

Let us explain in detail, how to obtain programs $\psi_{E,(i,j)}$ (where
$i,j\in\\{0,1\\}$) satisfying the claim of the above lemma for the relational
symbol $E$ and the gadget replacement $\gamma$ described in Example 3.2. The
programs $\phi_{E,(i,j)}$ are similar. All of them contain the following
rules:

$\displaystyle I_{0,1}(x,y)$ $\displaystyle\leftarrow E(x,y)$ $\displaystyle
I_{1,0}(x,y)$ $\displaystyle\leftarrow E(x,y)$ $\displaystyle I_{i,i}(x,x)$
$\displaystyle\leftarrow x=x$ $\displaystyle I_{i,j}(x,y)$
$\displaystyle\leftarrow I_{j,i}(y,x)$ $\displaystyle I_{i,k}(x,z)$
$\displaystyle\leftarrow I_{i,j}(x,y),I_{j,k}(y,z)$

for all $i$, $j$, $k\in\\{0,1\\}$. Further, fixing $i$ and $j$, we add into
$\phi_{E,(i,j)}$ the following two rules

$\displaystyle E_{i,j}(x,y)$ $\displaystyle\leftarrow
I_{i,0}(x,z),I_{j,1}(y,z)$ $\displaystyle E_{i,j}(x,y)$
$\displaystyle\leftarrow I_{i,1}(x,z),I_{j,0}(y,z)$

where $E_{i,j}$ is the output predicate. To recall the intuition,
$I_{i,j}(x,y)$ is derived if $x_{i}$ and $y_{j}$ were identified in the third
step of application of $\gamma$.

Observe that $I_{0,1}(x,y)$ and $I_{1,0}(x,y)$ are derived in $\mathbf{G}$ if
and only if $x$ and $y$ are connected by a path of odd length in $\mathbf{G}$,
and $I_{0,0}(x,y)$ and $I_{1,1}(x,y)$ are derived if and only if $x$ and $y$
are connected by a path of even length. This exactly corresponds to when
$x_{i}$ and $y_{j}$ are identified in the third step of application of
$\gamma$. Consequently, we get that, if $i\neq j$, $E_{i,j}(x,y)$ is derived
if and only if $x$ and $y$ are connected by a path of even length, and
$E_{i,i}$ is derived if and only if $x$ and $y$ are connected by a path of odd
length.

We are ready to prove Theorem 3.12. As mentioned above, it is enough to prove
this theorem for projective gadgets, i.e., the following lemma.

######  Lemma A.13.

For every projective gadget $\gamma$ of $\Sigma$ into $\Pi$, there is a
Datalog∪ reduction $\psi$ such that, for all $\Pi$-structures $\mathbf{A}$,
$\gamma(\mathbf{A})$ and $\psi(\mathbf{A})$ are homomorphically equivalent.

######  Proof A.14.

We construct a Datalog interpretation $\phi$ with output signature
$\Sigma^{\prime}$ (which we define below) and a union gadget $\upsilon$; the
required Datalog∪ reduction $\psi$ is the composition of $\phi$ and
$\upsilon$. As above, we assume that the structures $\mathbf{D}_{t}^{\gamma}$
are disjoint and that $\mathbf{D}^{\gamma}$ is their disjoint union.

The signature $\Sigma^{\prime}$ contains a type $g$ for each
$g\in\mathbf{D}^{\gamma}$, and a symbol $R_{g}$ for each $\Sigma$-symbol $R$
of arity $k$ and $(g\in\mathbf{D}^{\gamma})^{k}$, where $g_{i}$ is of type
$\operatorname{ar}_{R}(i)$ for all $i\in[k]$. The arity tuple of $R_{g}$ is
$(t_{1},\dots,t_{k})$ where $g_{i}\in\mathbf{D}^{\gamma}_{t_{i}}$ for all
$i\in[k]$. We define the Datalog interpretation $\phi$ using the following
components: For each $\Pi$-type $t$ and $g\in\mathbf{G}_{t}$, $\phi_{g}$ is
the Datalog program composed of the rule $D_{g}(x)\leftarrow x=x$, where $x$
is of type $t$. The relation $R_{g}$ is defined by the program $\phi_{R,g}$ as
in Lemma A.10, i.e., we let $\phi_{R_{g}}=\phi_{R,g}$. The union gadget
$\upsilon$ is defined by maps $(d,r)$ where $d$ maps $g$ to its $\Sigma$-type,
and $r(R_{g})=R$.

Let us now prove that $\upsilon\phi(\mathbf{A})$ and $\gamma(\mathbf{A})$ are
homomorphically equivalent. Observe that we have the following chain of
equivalent statements for all $k$-ary $\Sigma$-symbols $R$, and $k$-tuples $a$
and $g$ (such that $g_{i}\in\mathbf{D}_{s_{i}}^{\gamma}$ where $s_{i}$ is the
type of $a$, and the type of $g_{i}$ is $\operatorname{ar}_{R}(i)$):

$([a_{1};g_{1}],\dots,[a_{k};g_{k}])\in R^{\gamma(\mathbf{A})}\Leftrightarrow
a\in\phi_{R,g}^{\mathbf{A}}\Leftrightarrow\\\
R_{g}^{\phi(\mathbf{A})}\Leftrightarrow((a_{1};g_{1}),\dots,(a_{k};g_{k}))\in
R^{\upsilon\phi(\mathbf{A})}$

where the first equivalence is by Lemma A.10 and the last equivalence follows
from the definition of $\upsilon$. Hence, the mapping
$f\colon\upsilon\phi(\mathbf{A})\to\phi(\mathbf{A})$ defined by $f(a;g)=[a;g]$
is a homomorphism, and any mapping $g$ such that $g(b)\in f^{-1}(b)$ is a
homomorphism in the opposite direction.

We finish this subsection with two examples.

######  Example A.15.

Let us describe a Datalog∪ reduction obtained from the projective gadget
replacement $\gamma$ from Example A.3. The reduction is composed of a Datalog
interpretation $\phi$ and a union gadget $\upsilon$. The signature
$\Sigma^{\prime}$ from the above proof consists of two types, $0$ and $1$
(corresponding to the elements of $\mathbf{K}_{2}$), and binary relational
symbols $E_{i,j}$ for $i,j\in\\{0,1\\}$. The interpretation $\phi$ is given by
the tuple

$(\phi_{0},\phi_{1};\phi_{E,(0,0)},\phi_{E,(0,1)},\phi_{E,(1,0)},\phi_{E,(1,1)})$

where $\phi_{E,(i,j)}$ are the programs from Example A.12, and $\phi_{i}$, for
$i\in\\{0,1\\}$, are programs with a single rule $D_{i}(x)\leftarrow x=x$. The
union gadget $\upsilon$ is one of the constructions described in Example 3.3.
In this particular instance, it is defined by mappings $(d,r)$ where $d$ maps
both $0$ and $1$ to the only type of vertices of (di)graphs, and $r$ maps
$E_{i,j}$ to $E$.

We claim that the composition $\upsilon\circ\phi$ produces homomorphically
equivalent outputs to $\gamma$. To show that, let us assume for simplicity
that the input is a connected unoriented graph $\mathbf{G}$. We distinguish
two cases:

  1. (1)

$\mathbf{G}$ is bipartite, and $\gamma(\mathbf{G})\simeq\mathbf{K}_{2}$. Since
$\mathbf{G}$ is connected it splits to two parts $A$ and $B$ uniquely. Observe
that $x$ and $y$ are in the same part if and only if $x$ and $y$ are connected
by a path of even length, and they are in distinct parts if and only if $x$
and $y$ are connected by a path of odd length. Hence
$\upsilon\phi(\mathbf{G})$ is the complete bipartite graph with parts
$(A\times\\{0\\})\cup(B\times\\{1\\})$ and
$(A\times\\{1\\})\cup(B\times\\{0\\})$. Clearly, it is homomorphically
equivalent to $\mathbf{K}_{2}$.

  2. (2)

$\mathbf{G}$ contains an odd cycle, and $\gamma(\mathbf{G})$ is a loop. In
this case there is an odd path from $x$ to $x$ for each $x$. Hence all pairs
of elements $x$ and $y$ are connected by both odd and even path. This implies
that $\upsilon\phi(\mathbf{G})$ is a clique with all loops, and hence clearly
homomorphically equivalent to a loop.

Consequently, we have that $\upsilon\circ\phi$ is a reduction from
$\operatorname{CSP}(\mathbf{K}_{2})$ to
$\operatorname{CSP}(\mathbf{K}_{\infty})$.

######  Example A.16.

We can connect the above example with a rather easy Datalog reduction from
$\operatorname{CSP}(\mathbf{K}_{\infty})$ to $\operatorname{CSP}(\bot)$, which
is defined by the Datalog interpretation $\psi$ where $\psi_{C}$ is the
program with the rule $C\leftarrow E(x,x)$. Connecting these two reductions
together, we get that

$\operatorname{CSP}(\mathbf{K}_{2})\mathrel{\leq_{\text{Datalog}}}\operatorname{CSP}(\mathbf{K}_{\infty})\mathrel{\leq_{\text{Datalog}}}\operatorname{CSP}(\bot)$

where the full reduction from left to right is $\psi\circ\upsilon\circ\phi$
where $\upsilon$ and $\phi$ are as in the example above. Theorem 3.13 asserts
that
$\operatorname{CSP}(\mathbf{K}_{2})\mathrel{\leq_{\text{Datalog}}}\operatorname{CSP}(\bot)$,
i.e., that there is a Datalog interpretation $\phi^{\prime}$ and a union
gadget $\upsilon^{\prime}$ such that $\upsilon^{\prime}\circ\phi^{\prime}$
gives homomorphically equivalent outputs to $\psi\circ\upsilon$. In fact, the
union gadget $\upsilon^{\prime}$ is not needed in this case (due to a property
of the structure $\bot$). Let us describe how to construct this
$\phi^{\prime}$ from $\phi$, $\upsilon$, and $\psi$.

First, we switch the order of $\psi$ and $\upsilon$ in the same way as in
Example A.9 (except that the binary relations have a different name). The
Datalog interpretation $\psi^{\prime}$ has one component $\psi^{\prime}_{C}$
with rules

$C\leftarrow E_{0,0}\qquad C\leftarrow E_{1,1}.$

The Datalog interpretation $\phi^{\prime}$ obtained as a composition
$\psi^{\prime}\circ\phi$ is a valid reduction from
$\operatorname{CSP}(\mathbf{K}_{2})$ to
$\operatorname{CSP}(\mathbf{K}_{\infty})$. The only component of
$\phi^{\prime}$ is the Datalog program $\phi^{\prime}_{C}$ which is the union
of $\phi_{E,(0,0)}$, $\phi_{E,(1,1)}$, and the two rules of
$\psi^{\prime}_{C}$ above, i.e., the following program:

$\displaystyle I_{0,1}(x,y)$ $\displaystyle\leftarrow E(x,y)$ $\displaystyle
I_{i,k}(x,z)$ $\displaystyle\leftarrow I_{i,j}(x,y),I_{j,k}(y,z)$
$\displaystyle I_{1,0}(x,y)$ $\displaystyle\leftarrow E(x,y)$ $\displaystyle
E_{i,i}(x,y)$ $\displaystyle\leftarrow I_{i,0}(x,z),I_{i,1}(y,z)$
$\displaystyle I_{i,i}(x,x)$ $\displaystyle\leftarrow x=x$ $\displaystyle
E_{i,i}(x,y)$ $\displaystyle\leftarrow I_{i,1}(x,z),I_{i,0}(y,z)$
$\displaystyle I_{i,j}(x,y)$ $\displaystyle\leftarrow I_{j,i}(y,x)$
$\displaystyle C$ $\displaystyle\leftarrow E_{i,i}$

where $i,j,k\in\\{0,1\\}$. Note that this $\psi^{\prime}_{C}$ decides whether
the input has an odd cycle, or not. This program that we constructed by
joining our proofs is a more verbose version of much simpler Datalog program
solving $\operatorname{CSP}(\mathbf{K}_{2})$ described in Example 3.7.

Finally, let us remark that although we started with a projective gadget
replacement $\gamma$ and a Datalog interpretation $\phi$ of width $1$ that
does not use recursion (i.e., the graph whose vertices are relational symbols
appearing in a program, and there is an edge from $R$ to $S$ if $S$ appears in
the head of a rule which has $R$ in the body, does not have directed cycles),
the program $\psi^{\prime}_{C}$ has width $3$. It can be shown, using [35],
that this cannot be avoided: there is no Datalog program of width $2$ that
could be used instead of $\psi^{\prime}_{C}$, and no Datalog program that does
not use recursion that could be used instead of $\psi^{\prime}_{C}$.

###  A.3. The equivalence Datalog∪ and $k$-consistency reductions

The goal of this section is to prove Theorem 3.18. Let us briefly outline the
structure of the proof and the intuition behind it. We fix structures
$\mathbf{A}$, $\mathbf{B}$, and a parameter $k\geq 1$. The theorem claims two
implications about reductions from
$\operatorname{PCSP}(\mathbf{A},\mathbf{A}^{\prime})$ to
$\operatorname{PCSP}(\mathbf{B},\mathbf{B}^{\prime})$, namely that: (1) If
$\phi$ is a Datalog interpretation of width $k$ and $\gamma$ a gadget, such
that $\gamma\circ\phi$ is a reduction between the two promise CSPs, then so is
$\kappa_{k}^{\mathbf{A},\mathbf{B}}$. (2) If
$\kappa_{k}^{\mathbf{A},\mathbf{B}}$ is a reduction between the two promise
CSPs then so is $\pi_{\mathbf{B}}\circ\psi^{k,\mathbf{A}}$, where
$\pi_{\mathbf{B}}$ is the universal gadget, and $\psi^{k,\mathbf{A}}$ is a
Datalog interpretation of width $k$ which is based on the _canonical Datalog
program_ , and we define it below.

A feature of the proof is that neither of the constructed reductions depends
on the structures $\mathbf{A}^{\prime}$ and $\mathbf{B}^{\prime}$, which play
a role in the soundness of reductions. We compare the two reductions without
referring to these two structures, and show that in both implications the two
involved reductions, let us denote them by $\phi$ and $\psi$, satisfy
$\psi(\mathbf{X})\to\phi(\mathbf{X})$ for all instances $\mathbf{X}$. This
relation can be then used to transfer the soundness of $\psi$ to the soundness
of $\phi$. As usual, completeness is easier to show.

The proof leverages an algebraic intuition. First, we use a universal property
of $\pi_{\mathbf{B}}$ which, loosely speaking, says that $\pi_{\mathbf{B}}$ is
the ‘best gadget’ for a reduction from label cover to a
$\operatorname{PCSP}(\mathbf{B},{*})$. More precisely, reading the proof of
Theorem 5.8 in detail, we may observe that if a gadget $\gamma$ provides a
reduction from $\operatorname{PCSP}(\mathbf{P},{*})$ to
$\operatorname{PCSP}(\mathbf{B},{*})$, then $\pi_{\mathbf{B}}$ is also such a
reduction. We will actually show that this statement is provided by a
homomorphism $\gamma(\mathbf{X})\to\pi_{\mathbf{B}}(\mathbf{X})$ which exists
whenever $\gamma(\mathbf{P})\to\mathbf{B}$, i.e., that the soundness of
$\pi_{\mathbf{B}}$ can be derived from the soundness of $\gamma$ by the method
we described above.

Second, in both implications, we will need to compare different instances of
label cover whose types do not align well, e.g., the elements of
$\kappa_{k}^{\mathbf{A}}(\mathbf{X})$ are of types $\mathcal{F}_{K}$, which is
a subset of partial homomorphism from $K$ to $\mathbf{A}$ for some
$K\in\binom{X}{\leq k}$, while the elements of
$\psi^{k,\mathbf{A}}(\mathbf{X})$ are of types which correspond to relations
$R\subseteq A^{m}$ for $m\leq k$. The set $\mathcal{F}_{K}$ and the relation
$R$ can be compared using known facts about Datalog and consistency.
Nevertheless, that these sets relate to each other is not enough to provide a
homomorphism between the two label cover instances for formal reasons.
Instead, we relax the notion of a homomorphism (again guided by an algebraic
intuition) to a notion of a ‘weak homomorphism’.111111If a label cover
instance is interpreted as a _minor condition_ , these ‘weak homomorphisms’
correspond exactly to ‘syntactic implications between minor conditions’. We
express these ‘weak homomorphisms’ in combinatorial language as follows:
‘$\mathbf{S}$ maps weakly to $\mathbf{T}$’ if
$\mathbf{S}\to\pi_{\mathbf{P}}(\mathbf{T})$; recall, that $\mathbf{P}$ denotes
the template of the label cover problem. It turns out that the existence of
this homomorphism is equivalent to existence of homomorphisms
$\pi_{\mathbf{B}}(\mathbf{S})\to\pi_{\mathbf{B}}(\mathbf{T})$ for all
structures $\mathbf{B}$. Consequently, we get that a ‘weak homomorphism’ is
mapped by a universal gadget to a normal homomorphism which we will use in our
proof. In this instance, we want to show that
$\kappa_{k}^{\mathbf{A}}(\mathbf{X})\to\pi_{\mathbf{P}}\psi^{k,\mathbf{A}}(\mathbf{X})$
which is a straightforward technical exercise (using the connection between
$\mathcal{F}_{K}$ and $R$ outlined above). Alternatively, we could again
leverage the universality of $\pi_{\mathbf{P}}$ by observing that we can
recover $\psi^{k,\mathbf{A}}(\mathbf{X})$ from
$\kappa_{k}^{\mathbf{A}}(\mathbf{X})$ by application of a simple gadget
reduction $\gamma$.

The soundness of $\kappa_{k}^{\mathbf{A},\mathbf{B}}$ in the other implication
is obtained in a similar way. Let us recall that our goal is to show that
$\gamma\phi(\mathbf{X})\to\kappa_{k}^{\mathbf{A},\mathbf{B}}$ where $\phi$ is
a Datalog interpretation of width $k$ and $\gamma$ is a gadget. We would like
to use ‘weak homomorphisms’ again to compare $\phi$ and
$\kappa_{k}^{\mathbf{A}}$, but in order to do that, the output of $\phi$ needs
to be a label cover instance. We reduce to that case by decomposing
$\gamma\circ\phi$ as
$\gamma_{\phi(\mathbf{A})}\circ\rho^{\phi(\mathbf{A})}\circ\phi$ using Lemma
A.5, and hence we turn $\gamma\circ\phi$ into
$\gamma^{\prime}\circ\phi^{\prime}$ where
$\gamma^{\prime}=\gamma_{\phi(\mathbf{A})}$ and
$\phi^{\prime}=\rho^{\phi(\mathbf{A})}\circ\phi$. We then prove that

$\phi^{\prime}(\mathbf{X})\to\pi_{\mathbf{P}}\kappa_{k}^{\mathbf{A}}(\mathbf{X})$
(A.1)

for all structures $\mathbf{X}$ with the same signature as $\mathbf{A}$. This
statement is again proved by leveraging the known connection of Datalog and
consistency. The proof of the implication is then concluded by the
universality of $\pi_{\mathbf{B}}$.

Incidentally, the proof of (A.1) applies without any significant changes to
the canonical Datalog program $\psi^{k,\mathbf{A}}$ in place of
$\phi^{\prime}$. Consequently, the structures
$\pi_{\mathbf{B}}\psi^{k,\mathbf{A}}(\mathbf{X})$ and
$\kappa_{k}^{\mathbf{A},\mathbf{B}}(\mathbf{X})$ are homomorphically
equivalent (in fact, with a bit more effort, it can be shown that they are
isomorphic). This observation provides ground for saying that $k$-consistency
reduction _is_ a Datalog reduction (as opposed to only being equivalent to
one). And we also use it to derive the completeness of
$\pi_{\mathbf{B}}\circ\psi^{k,\mathbf{A}}$ from the completeness of
$\kappa_{k}^{\mathbf{A},\mathbf{B}}$.

The rest of this appendix is a formalisation of the ideas described above. The
proofs are presented in full technical detail. We start by introducing some
notation, introducing the components of our reductions, and recalling known
results.

####  A.3.1. Notation

We will extensively use a functional notation for tuples, i.e., we view $w\in
X^{n}$ as a function $w\colon[n]\to X$. In particular, $\operatorname{im}w$ is
the set of all entries of $w$, i.e.,
$\operatorname{im}w=\\{w_{1},\dots,w_{n}\\}$, and if $\pi\colon[m]\to[n]$ then
$w\circ\pi=(w_{\pi(1)},\dots,w_{\pi(n)})$. We write $R\circ\pi$ for the
$m$-ary relation $\\{a\circ\pi\mid a\in R\\}$. Finally, we will denote by
$X^{\leq k}$ the set of all tuples of elements from $X$ of length at most $k$.

####  A.3.2. The universality of gadgets

Let us start with the universality of gadgets $\pi_{\mathbf{B}}$, i.e., the
following lemma. Let us reiterate that the intuition is provided by [6] which
implicitly claims that if a gadget reduction is a valid reduction from a
reduct of label cover to $\operatorname{PCSP}(\mathbf{B},{*})$ then so is
$\pi_{\mathbf{B}}$.

Fix a reduct of label cover signature $\Sigma$, and let $\mathbf{P}^{\Sigma}$
denote the $\Sigma$-reduct of the label cover template $\mathbf{P}$, and fix a
structure $\mathbf{B}$.

######  Lemma A.17.

If $\gamma$ is a gadget such that $\gamma(\mathbf{P}^{\Sigma})\to\mathbf{B}$,
then for every $\mathbf{S}$,
$\gamma(\mathbf{S})\to\pi_{\mathbf{B}}(\mathbf{S})$.

######  Proof A.18.

Let $b\colon\gamma(\mathbf{P}^{\Sigma})\to\mathbf{B}$ be a homomorphism. Since
$\gamma$ is not necessarily projective, we use the non-projective version of
$\pi_{\mathbf{B}}$ as well (i.e., Definition 3.4). We define a homomorphism
$h\colon\gamma(\mathbf{S})\to\pi_{\mathbf{B}}(\mathbf{S})$ by

$h([x;g])=[x;d_{g}]$

for each $x\in S_{X}$ and $g\in\mathbf{D}_{X}^{\gamma}$, or $x\in
E_{\sigma}^{\mathbf{S}}$ and $g\in\mathbf{E}_{\sigma}^{\gamma}$, where $d_{g}$
is defined by $d_{g}(a)=b([a;g])$ in either case, i.e., both as a map $X\to B$
and $E_{\sigma}^{\mathbf{P}}\to B$. We need to show that $h$ is a well-defined
homomorphism which is relatively straightforward.

Let us start with checking that $h$ preserves the equality constraints
introduced to $\gamma(\mathbf{S})$ in step (3) of the gadget replacement.
Assume that $(x;p_{E_{\sigma},i}^{\gamma}(g))=(x_{i};g)$ is one of these
constraints, i.e., that $x\in E_{\sigma}^{\mathbf{S}}$, and
$g\in\mathbf{D}_{\operatorname{ar}_{E_{\sigma}}(i)}$. For simplicity, we will
write $p^{\gamma}$ instead of $p_{E_{\sigma},i}^{\gamma}$, and let us write
$p_{i}\colon E_{\sigma}^{\mathbf{P}}\to P_{\operatorname{ar}_{R}(i)}$ for the
$i$-th projection. Observe that, for all $a\in E_{\sigma}^{\mathbf{P}}$,

$d_{g}p_{i}(a)=b([a_{i};g])=b([a;p^{\gamma}(g)])=d_{p^{\gamma}(g)}(a)$

where the middle equality holds since $a\in E_{\pi}^{\mathbf{P}}$. From the
definition of $\pi_{\mathbf{B}}$, we have that $[x;d_{g}\circ
p_{i}]=[x_{i};d_{g}]$, which, together with the above, gives that
$[x;d_{p(g)}]=[y;d_{g}]$ as we wanted to show.

To show that $h$ preserves relations, let

$([x_{1};g_{1}],\dots,[x_{\ell};g_{\ell}])\in R^{\gamma(\mathbf{X})}.$

Since $h$ is well-defined, we may assume without loss of generality that
$x_{1}=\dots=x_{\ell}=x$ and that $(g_{1},\dots,g_{\ell})=g$ is in the
$R$-relation of the corresponding component of $\gamma$. Furthermore, let us
assume that $x$ is an element of type $X$, and $g\in
R^{\mathbf{D}_{X}^{\gamma}}$ — the other case, when $x\in
E_{\sigma}^{\mathbf{S}}$ for some $\sigma$ is analogous. Since
$h([x;g_{i}])=[x;d_{g_{i}}]$, it is enough to prove that
$(d_{g_{1}},\dots,d_{g_{\ell}})\in R^{\mathbf{B}^{X}}$ which is immediate from
the definition of the power $\mathbf{B}^{X}$ since $g\in
R^{\mathbf{D}_{X}^{\gamma}}$ and $b$ is a homomorphism.

The following is a direct corollary of the above.

######  Lemma A.19.

Let $\mathbf{S}$ and $\mathbf{T}$ be two label cover instances such that
$\mathbf{S}\to\pi_{\mathbf{P}}(\mathbf{T})$. Then
$\pi_{\mathbf{B}}(\mathbf{S})\to\pi_{\mathbf{B}}(\mathbf{T})$ for all
structures $\mathbf{B}$.

######  Proof A.20.

Since $\pi_{\mathbf{B}}$ is monotone, we have that
$\pi_{\mathbf{B}}(\mathbf{S})\to\pi_{\mathbf{B}}\pi_{\mathbf{P}}(\mathbf{T})$.
Observe that $\pi_{\mathbf{X}}(\mathbf{P})\to\mathbf{X}$ for all $\mathbf{X}$
by mapping $[x,p]\mapsto p(x)$. Consequently,
$\pi_{\mathbf{B}}\circ\pi_{\mathbf{P}}$ is a gadget such that
$\pi_{\mathbf{B}}\pi_{\mathbf{P}}(\mathbf{P})\to\mathbf{B}$, and hence the
previous lemma applies, and we get
$\pi_{\mathbf{B}}\pi_{\mathbf{P}}(\mathbf{T})\to\pi_{\mathbf{B}}(\mathbf{T})$,
and the desired by composing the two homomorphisms.

Let us also note that the converse of the lemma is true, though it is not
necessary for our proof: If
$\pi_{\mathbf{B}}(\mathbf{S})\to\pi_{\mathbf{B}}(\mathbf{T})$ for all
$\mathbf{B}$, then in particular
$\pi_{\mathbf{P}}(\mathbf{S})\to\pi_{\mathbf{P}}(\mathbf{T})$, and it is not
hard to observe that $\mathbf{S}\to\pi_{\mathbf{P}}(\mathbf{S})$
(alternatively, we can argue that this homomorphism follows from the
universality of $\pi_{\mathbf{P}}$ since the identity mapping is a gadget
replacement), and therefore $\mathbf{S}\to\pi_{\mathbf{P}}(\mathbf{T})$.

####  A.3.3. Canonical Datalog interpretation

We define the canonical interpretation which is based on the _canonical
Datalog program_ $\psi$ of width $k$ for a structure $\mathbf{A}$. We define
this Datalog program as a set of rules without an output predicate — the
Datalog interpretation will use copies of this program with different output
predicates as components.

######  Definition A.21.

Fix a structure $\mathbf{A}$ and $k\geq 1$. We denote by
$\Delta^{k,\mathbf{A}}$ the set of all relations $R\subseteq A^{m}$, where
$m\leq k$, that are definable in $\mathbf{A}$ by a Datalog program of width at
most $k$, i.e., all relations $R$ of the form $R=\phi(\mathbf{A})$ where
$\phi$ is a Datalog program of width at most $k$.

The signature of the _canonical program_ $\psi$ for $\mathbf{A}$ of width $k$
consists (apart from the basic symbols of $\mathbf{A}$) of a symbol $R$ for
each $R\in\Delta^{k,\mathbf{A}}$. We treat each such relation as an abstract
symbol of the same arity as the Datalog program $\phi$ that defined it. The
rules of the canonical Datalog are all the rules (with at most $k$ variables)
that are satisfied in $\mathbf{A}$ when each rule is interpreted as an
implication $t_{0}\leftarrow t_{1}\wedge\dots\wedge t_{r}$ where $t_{0}$ is
the head and $t_{1},\dots,t_{r}$ is the body (and the basic symbols $R$ are
interpreted as $R^{\mathbf{A}}$).

With this program at hand, we can construct the canonical Datalog
interpretation.

######  Definition A.22.

Fix a structure $\mathbf{A}$ and $k\geq 1$. The _canonical Datalog
interpretation_ $\psi^{k,\mathbf{A}}$ is defined as follows. The output of
$\psi^{k,\mathbf{A}}$ is a reduct of a label cover instance. More precisely,
the output signature consists of a type $R$ for each
$R\in\Delta^{k,\mathbf{A}}$ which is viewed as the set $R\subseteq A^{m}$, and
a binary symbol $E_{\pi}$ for each $\pi\colon R\to S$ of the form
$\pi(a)=a\circ p$ for some $p\colon[m_{S}]\to[m_{R}]$ where $m_{R}$ and
$m_{S}$ denote the arity of $R$ and $S$, respectively.

The domains are defined by the Datalog programs $\psi^{k,\mathbf{A}}_{R}$
obtained from the canonical Datalog program by designing $R$ as the output.
The relation $E_{\pi}$ where $\pi\colon R\to S$ is of the form $\pi(a)=a\circ
p$ is defined by the program $\psi^{k,\mathbf{A}}_{E_{\pi}}$ obtained from the
canonical program by adding the rule

$E_{\pi}(x_{1},\dots,x_{n},x_{p_{\pi}(1)},\dots,x_{p_{\pi}(m)})\leftarrow
R(x_{1},\dots,x_{n}).$

Note that $\psi^{k,\mathbf{A}}_{R}(\mathbf{A})=R$ for each
$R\in\Delta^{k,\mathbf{A}}$, and that
$\psi^{k,\mathbf{A}}_{E_{\pi}}(\mathbf{A})=\\{(a,a\circ p)\mid a\in R\\}$.
Hence $\psi^{k,\mathbf{A}}(\mathbf{A})$ is a reduct of $\mathbf{P}$ whose
domains consist of all relations definable in $\mathbf{A}$ by a Datalog
program of width $k$.

Let us recall a few known facts about the connection between the
$k$-consistency algorithm and Datalog program of width $k$. This connection is
well understood, and we refer to, e.g., Kolaitis and Vardi [34]; Feder and
Vardi [26] for more details. We will use three lemmas which are either
implicitly, or explicitly proved in [34] (see, e.g., [34, Theorem 4.8]).

######  Lemma A.23 ([34]).

Let $\mathbf{A}$ and $\mathbf{X}$ are structures with the same signature,
$k\geq 1$, and $\mathcal{F}_{K}$ denote the sets output by the $k$-consistency
enforcement applied on the instance $\mathbf{X}$, i.e., $\mathcal{F}_{K}$ is
the type of the variable $v_{K}\in\kappa_{k}^{\mathbf{A}}(\mathbf{X})$. Let
$w$ be a tuple such that $\operatorname{im}w\in\binom{X}{\leq k}$, and
$R=\mathcal{F}_{\operatorname{im}w}\circ w$.

  1. (A.23(1))

For each Datalog program $\phi$ of width at most $k$, if
$w\in\phi(\mathbf{X})$, then $a\in\phi(\mathbf{A})$ for all $a\in
R$.121212This applies to all tuples in $w\in\phi(\mathbf{X})$ since if $\phi$
has width at most $k$, $\operatorname{im}w$ has at most $k$ elements.

  2. (A.23(2))

If $w\in X^{\leq k}$, then $R$ is the smallest relation
$S\in\Delta^{k,\mathbf{A}}$ (w.r.t., inclusion) such that $w\in S$.

  3. (A.23(3))

If $w\in X^{\leq k}$, then $w\in\psi^{k,\mathbf{A}}_{R}(\mathbf{X})$.

####  A.3.4. Soundness

We fix structures $\mathbf{A}$ and $\mathbf{B}$, and a parameter $k\geq 1$. We
first prove the implication claiming that if
$\kappa_{k}^{\mathbf{A},\mathbf{B}}$ is a reduction then so is
$\pi_{\mathbf{B}}\circ\psi^{k,\mathbf{A}}$. As outlined above, the first step
is to provide the following homomorphism.

######  Lemma A.24.

For each structure $\mathbf{X}$ with the same signature as $\mathbf{A}$,

$\kappa_{k}^{\mathbf{A}}(\mathbf{X})\to\pi_{\mathbf{T}}\psi^{k,\mathbf{A}}(\mathbf{X}).$

Intuitively, the above homomorphism exists since
$\kappa_{k}^{\mathbf{A}}(\mathbf{X})$ is essentially a substructure of
$\psi^{k,\mathbf{A}}(\mathbf{X})$ if we were allowed to map a variable $v_{K}$
where $K=\\{x_{1},\dots,x_{\ell}\\}$ to a tuple
$w=(x_{1},\dots,x_{\ell})\in\psi^{k,\mathbf{A}}_{R}(\mathbf{X})$ where
$R=\mathcal{F}_{K}\circ w$ (which is Datalog definable by Lemma A.23(2)). The
issue is that for a proper homomorphism, we would need that
$R=\mathcal{F}_{K}$. Instead we provide a mapping
$\kappa_{k}^{\mathbf{A}}(\mathbf{X})\to\pi_{\mathbf{P}}\psi^{k,\mathbf{A}}(\mathbf{X})$
by choosing a bijection between $K$ and $[\ell]$ which induces a bijection
between $R$ and $\mathcal{F}_{K}$.

In the formal proof, we will use the following technical lemma.

######  Lemma A.25.

Assume that $\mathbf{S}$ is a label cover instance. For all $s\in S_{X_{s}}$,
$t\in S_{X_{t}}$, $f_{s}\colon X_{s}\to Y_{s}$, $f_{t}\colon X_{t}\to Y_{t}$,
$\sigma\colon X_{s}\to X_{t}$, and $\sigma^{\prime}\colon Y_{s}\to Y_{t}$ such
that $\sigma^{\prime}\circ f_{s}=f_{t}\circ\sigma$, and $(s,t)\in
E_{\sigma}^{\mathbf{S}}$, we have

$([s,f_{s}],[t,f_{t}])\in E_{\sigma^{\prime}}^{\pi_{\mathbf{P}}(\mathbf{S})}.$

######  Proof A.26.

First observe that $[t,f_{t}]=[s,f_{t}\circ\sigma]$ and
$([s,f_{s}],[s,\sigma^{\prime}\circ f_{s}])\in
E_{\sigma^{\prime}}^{\pi_{\mathbf{P}}(\mathbf{S})}$ follows directly from the
definition of $\pi_{\mathbf{P}}(\mathbf{S})$. Using the assumption
$\sigma^{\prime}\circ f_{s}=f_{t}\circ\sigma$, the former observation gives
that $[t,f_{t}]=[s,\sigma^{\prime}\circ f_{s}]$. This equality together with
the latter observation yields the desired.

######  Proof A.27 (Proof of Lemma A.24).

To simplify the notation, let us write $\kappa$ instead of
$\kappa_{k}^{\mathbf{A}}$ and $\psi$ instead of $\psi^{k,\mathbf{A}}$.

To define a homomorphism
$h\colon\kappa(\mathbf{X})\to\pi_{\mathbf{P}}\psi(\mathbf{X})$. Fix a
bijection $w_{K}\colon[\lvert K\rvert]\to K$ for each $K\in\binom{X}{\leq k}$
and let $w_{K}^{-1}$ denote the inverse of this bijection. By Lemma A.23(3),
$w_{K}\in\psi_{R_{K}}(\mathbf{X})$ where $R_{K}=\mathcal{F}_{K}\circ w_{K}$.
Hence we may interpret $w_{K}$ as an element of type $R_{K}$ in
$\psi(\mathbf{X})$. We define $h$ by

$h(v_{K})=[w_{K},p_{K}]$

where $p_{K}\colon R_{K}\to\mathcal{F}_{K}$ is defined by $p_{K}(a)=a\circ
w_{K}^{-1}$. In the rest of the proof, we check that $h$ is indeed a
homomorphism.

To show that $h$ preserves the relations, we need to show that if
$(v_{K},v_{L})\in E_{\sigma}^{\kappa(\mathbf{X})}$, i.e., if $L\subset K$ and
$\sigma(f)=f|_{L}$, then $([w_{K};p_{K}],[w_{L};p_{L}])\in
E_{\sigma}^{\psi(\mathbf{X})}$. By Lemma A.25, it is enough to provide
$\sigma^{\prime}\colon R_{K}\to R_{L}$ such that
$p_{L}\circ\sigma^{\prime}=\sigma\circ p_{K}$, and $(w_{K},w_{L})\in
E_{\sigma^{\prime}}^{\psi(\mathbf{X})}$. We let $p\colon[\lvert
L\rvert]\to[\lvert K\rvert]$ to be the mapping $p=w_{K}^{-1}\circ w_{L}$,
i.e., the mapping which for each $i$ returns the index of $w_{L}(i)$ in
$w_{K}$, and define $\sigma^{\prime}$ by $\sigma^{\prime}(a)=a\circ p$.
Clearly,

$w_{K}\circ p=w_{K}\circ w_{K}^{-1}\circ w_{L}=w_{L},$

and consequently, $(w_{K},w_{L})\in E_{\sigma^{\prime}}^{\psi(\mathbf{X})}$.
Next, we check that $\sigma^{\prime}$ satisfies the equality above. Let $a\in
R_{K}$, then

$p_{L}\sigma^{\prime}(a)=a\circ p\circ w_{L}^{-1}=a\circ w_{K}^{-1}\circ
w_{L}\circ w_{L}^{-1}=(a\circ w_{K}^{-1})|_{L}=\sigma p_{K}(a)$

as we wanted to show.

The following corollary, which is enough to provide soundness of
$\pi_{\mathbf{B}}\circ\psi^{k,\mathbf{A}}$ assuming soundness of
$\kappa_{k}^{\mathbf{A},\mathbf{B}}$, follows directly from the above lemma
and Lemma A.19.

######  Corollary A.28.

For every structure $\mathbf{X}$ with the same signature as $\mathbf{A}$,

$\kappa_{k}^{\mathbf{A},\mathbf{B}}(\mathbf{X})\to\pi_{\mathbf{B}}\psi^{k,\mathbf{A}}(\mathbf{X})$

We move onto proving soundness of $\kappa_{k}^{\mathbf{A},\mathbf{B}}$
assuming that there is a Datalog interpretation $\phi$ and a gadget $\gamma$
such that $\gamma\circ\phi$ is a valid reduction. The first step is the
universality of $\kappa_{k}$ phrased in the following lemma in which we,
again, leverage the connection of Datalog and $k$-consistency algorithm.

######  Lemma A.29.

Let $\phi$ be a Datalog interpretation of width at most $k$, then for every
structure $\mathbf{X}$ with the same signature as $\mathbf{A}$,

$\rho^{\phi(\mathbf{A})}\phi(\mathbf{X})\to\pi_{\mathbf{P}}\kappa_{k}^{\mathbf{A}}(\mathbf{X}).$

######  Proof A.30.

Let us assume that $\Sigma$ is the output signature of
$\rho^{\phi(\mathbf{A})}$, which is a reduct of the label cover signature, and
that the domains of $\mathbf{A}$ are disjoint. First, we derive a few
properties of the Datalog interpretation $\phi^{\prime}$ obtained as a
composition $\rho^{\phi(\mathbf{A})}\circ\phi$ (see Lemma A.7(2)). Namely,
$\phi^{\prime}$ is obtained as follows: For each type $t$, and each relational
symbol $R$ (in the signature of $\phi(\mathbf{A})$), we let
$\phi^{\prime}_{A_{t}}=\phi_{t}$ and
$\phi^{\prime}_{R^{\mathbf{A}}}=\phi_{R}$. These programs define the domains
of $\phi^{\prime}(\mathbf{X})$. The relation corresponding to $E_{\sigma}$,
for a symbol $R$ of arity $\ell$, $i\in[\ell]$, and $\sigma\colon
R^{\mathbf{A}}\to A_{\operatorname{ar}(i)}$ is the $i$-th projection, is
defined by the program $\phi^{\prime}_{E_{\sigma}}$ which is obtained from
$\phi_{R}$ by adding the rule

$E_{\sigma}(x_{1},\dots,x_{m},x_{p_{\sigma}(1)},\dots,x_{p_{\sigma}(n_{i})})\leftarrow
R(x_{1},\dots,x_{m})$ (A.2)

where $n_{i}$ is the arity of $\phi_{\operatorname{ar}_{R}(i)}$ and
$p_{\sigma}\colon[n_{i}]\to[m]$ is the mapping that selects the $n_{i}$
consecutive coordinates of $R$ that corresponds to the coordinates defining
the $i$-th projection of $R$, i.e., $p_{\sigma}(x)=x+\sum_{j<i}n_{j}$ (see
Definition 3.5), and changing the output predicate accordingly. Remark that
$\phi^{\prime}$ is not necessarily of width $k$ — we will only use the fact
that $\phi^{\prime}_{t}$ and $\phi^{\prime}_{R}$ are of width $k$ and that
$\phi^{\prime}_{E_{\sigma}}$ is of the form above.

From now on we will we work with the interpretation $\phi^{\prime}$ instead of
$\phi$, and write $\kappa$ instead of $\kappa_{k}^{\mathbf{A}}$. We define a
homomorphism
$h\colon\phi^{\prime}(\mathbf{X})\to\pi_{\mathbf{P}}\kappa(\mathbf{X})$. We
have to be a bit careful, since the domains of $\phi^{\prime}(\mathbf{X})$ are
not necessarily disjoint. To avoid confusion, we will define $h$ as a
collection of mappings
$h_{T}\colon\phi^{\prime}_{T}(\mathbf{X})\to\kappa(\mathbf{X})$ where $T$ is a
$\Sigma$-type. Note that each such type corresponds to a domain of
$\phi^{\prime}(\mathbf{A})$, i.e., $T$ is a Datalog definable relation in
$\mathbf{A}$. By Lemma A.23(1), we have that
$\mathcal{F}_{\operatorname{im}w}\circ
w\subseteq\phi^{\prime}_{T}(\mathbf{A})=T$ for each
$w\in\phi^{\prime}_{T}(\mathbf{X})$. This observation allows us to define
$h_{T}$ as

$h_{T}(w)=[v_{\operatorname{im}w};p_{w}]$

where $p_{w}\colon\mathcal{F}_{K}\to T$ is defined by $p_{w}(f)=f\circ w$.

Let us prove that $h$ is indeed a weak homomorphism. We use Lemma A.25 to show
that if $(w,w^{\prime})\in E_{\sigma}^{\phi^{\prime}(\mathbf{X})}$, then
$([v_{\operatorname{im}w};p_{w}],[v_{\operatorname{im}w^{\prime}};p_{w^{\prime}}])\in
E_{\sigma}^{\pi_{\mathbf{P}}\kappa(\mathbf{X})}$, i.e., we show that there is
$\sigma^{\prime}$ such that
$(v_{\operatorname{im}w},v_{\operatorname{im}w^{\prime}})\in
E_{\sigma^{\prime}}^{\kappa(\mathbf{X})}$ and

$p_{w^{\prime}}\circ\sigma^{\prime}=\sigma\circ p_{w}.$ (A.3)

Note that $\sigma\colon R\to S$ is of the form $\sigma(a)=a\circ p_{\sigma}$
and $w^{\prime}=w\circ p_{\sigma}$ since
$E_{\sigma}^{\phi^{\prime}(\mathbf{X})}$ is defined by the rule (A.2).
Consequently $\operatorname{im}w^{\prime}\subseteq\operatorname{im}w$, hence
$(\operatorname{im}w,\operatorname{im}w^{\prime})\in E_{\sigma^{\prime}}$
where
$\sigma^{\prime}\colon\mathcal{F}_{\operatorname{im}w}\to\mathcal{F}_{\operatorname{im}w^{\prime}}$
is the restriction $\sigma^{\prime}(f)=f|_{\operatorname{im}w^{\prime}}$. Let
us check the identity (A.3) by applying both sides to
$f\in\mathcal{F}_{\operatorname{im}w}$:

$p_{w^{\prime}}\sigma^{\prime}(f)=p_{w^{\prime}}(f|_{\operatorname{im}w^{\prime}})=f\circ
w^{\prime}=f\circ w\circ p_{\sigma}=\sigma(f\circ w)=\sigma p_{w}(f).$

This concludes the proof.

We now conclude the proof of the soundness of
$\kappa_{k}^{\mathbf{A},\mathbf{B}}$ assuming soundness of $\gamma\circ\phi$
with the following corollary.

######  Corollary A.31.

Let $\phi$ be a Datalog interpretation of width at most $k$ and $\gamma$ be a
gadget, such that $\gamma\phi(\mathbf{A})\to\mathbf{B}$. For every structure
$\mathbf{X}$ with the same signature as $\mathbf{A}$,

$\gamma\phi(\mathbf{X})\to\kappa_{k}^{\mathbf{A},\mathbf{B}}(\mathbf{X})$

######  Proof A.32.

Decompose $\gamma$ as $\gamma_{\phi(\mathbf{A})}\circ\rho^{\phi(\mathbf{A})}$
using Lemma A.5. Consequently, we have

$\rho^{\phi(\mathbf{A})}\phi(\mathbf{X})\to\pi_{\mathbf{P}}\kappa_{k}^{\mathbf{A}}(\mathbf{X})$
(A.4)

by Lemma A.29. Observe that $\gamma_{\phi(\mathbf{A})}$ maps the corresponding
reduct of the label cover template $\rho^{\phi(\mathbf{A})}\phi(\mathbf{A})$
to $\mathbf{B}$, which allows us to apply Lemma A.17 to get a homomorphism

$\gamma\phi(\mathbf{X})=\gamma_{\phi(\mathbf{A})}\rho^{\phi(\mathbf{A})}\phi(\mathbf{X})\to\pi_{\mathbf{B}}\rho^{\phi(\mathbf{A})}\phi(\mathbf{X}).$

Further, by Lemma A.19 and (A.4) we have that

$\pi_{\mathbf{B}}\rho^{\phi(\mathbf{A})}\phi(\mathbf{X})\to\pi_{\mathbf{B}}\kappa_{k}^{\mathbf{A}}(\mathbf{X})=\kappa_{k}^{\mathbf{A},\mathbf{B}}(\mathbf{X})$

which together with the above homomorphism gives the desired.

####  A.3.5. Completeness

Let us start with the completeness of the $k$-consistency reduction which can
be proved by the following straightforward argument.

######  Lemma A.33.

If $\mathbf{X}\to\mathbf{A}$, then
$\kappa_{k}^{\mathbf{A},\mathbf{B}}(\mathbf{X})\to\mathbf{B}$.

######  Proof A.34.

Let $g\colon\mathbf{X}\to\mathbf{A}$ be a homomorphism. First, we observe
that, for each $K\in\binom{X}{\leq k}$, the restriction $g|_{K}$, satisfies
$g|_{K}\in\mathcal{F}_{K}$: this is since the restrictions are locally
consistent partial homomorphisms and will never be removed from
$\mathcal{F}_{K}$. We use this observation to define a homomorphism
$h\colon\kappa^{\mathbf{A},\mathbf{B}}_{k}(\mathbf{A})\to\mathbf{B}$. We
define $h$ by

$h([v_{K};b])=b(g|_{K})$

where $K\in\binom{X}{\leq k}$ and $b\in B^{\mathcal{F}_{K}}$. We need to show
that it is well-defined, i.e., that the value of $h$ does not depend on the
choice of representative. It is enough to check that for pairs $(v_{K};b)$ and
$(v_{L};b^{\prime})$ where $L\subset K$ and $b(f)=b^{\prime}(f|_{L})$. In that
case, we have

$h([v_{K};b])=b(g|_{K})=b^{\prime}((g|_{K})|_{L})=b^{\prime}(g|_{L})=h([v_{L};b^{\prime}]).$

The fact that $h$ preserves relations is immediate.

The completeness of $\pi_{\mathbf{B}}\circ\psi^{k,\mathbf{A}}$ can be proved
in several ways. First, observing that both reductions are monotone, it is
enough to check that
$\pi_{\mathbf{B}}\psi^{k,\mathbf{A}}(\mathbf{A})\to\mathbf{B}$, which can be
done in two steps by checking that
$\psi^{k,\mathbf{A}}(\mathbf{A})\to\mathbf{P}$ and that
$\pi_{\mathbf{B}}(\mathbf{P})\to\mathbf{B}$. Alternatively, we may observe the
following fact which follows from our proofs of soundness, and allows us to
infer the completeness of $\pi_{\mathbf{B}}\circ\psi^{k,\mathbf{A}}$ from the
completeness of $\kappa_{k}^{\mathbf{A},\mathbf{B}}$.

######  Lemma A.35.

For all structures $\mathbf{X}$ of the same signature as $\mathbf{A}$,
$\pi_{\mathbf{B}}\psi^{k,\mathbf{A}}(\mathbf{X})$ and
$\kappa_{k}^{\mathbf{A},\mathbf{B}}(\mathbf{X})$ are homomorphically
equivalent.

######  Proof A.36.

A homomorphism
$\kappa_{k}^{\mathbf{A},\mathbf{B}}(\mathbf{X})\to\pi_{\mathbf{B}}\psi^{k,\mathbf{A}}(\mathbf{X})$
is proved in Corollary A.28. A homomorphism
$\psi^{k,\mathbf{A}}(\mathbf{X})\to\pi_{\mathbf{P}}\kappa_{k}^{\mathbf{A}}(\mathbf{X})$
is constructed during the proof of Lemma A.29: observe that the Datalog
interpretation $\psi^{k,\mathbf{A}}$ has all the properties of $\phi^{\prime}$
that have been used in the proof of the lemma, and hence the same proof works
here as well. Consequently, we get a homomorphism
$\pi_{\mathbf{B}}\psi^{k,\mathbf{A}}(\mathbf{X})\to\kappa_{k}^{\mathbf{A},\mathbf{B}}(\mathbf{X})$
by Lemma A.19.

####  A.3.6. Putting everything together

We conclude this appendix with a formal proof of the theorem which we recall
for convenience.

See 3.18

######  Proof A.37.

We start with the implication (1) $\to$ (2). We need to prove that
$\kappa_{k}^{\mathbf{A},\mathbf{B}}$ is sound and complete reduction between
the two promise CSPs. Completeness is proved in Lemma A.33, and the soundness
follows from Corollary A.31 in the following way: Assume that
$\kappa_{k}^{\mathbf{A},\mathbf{B}}(\mathbf{X})\to\mathbf{B}^{\prime}$ then by
the corollary, we have that
$\gamma\phi(\mathbf{X})\to\kappa_{k}^{\mathbf{A},\mathbf{B}}(\mathbf{X})\to\mathbf{B}^{\prime}$,
and hence $\mathbf{X}\to\mathbf{A}^{\prime}$ since $\gamma\circ\phi$ is sound.

The implication (2) $\to$ (1) is proved in a similar way. We let
$\phi=\psi^{k,\mathbf{A}}$ and $\gamma=\pi_{\mathbf{B}}$. Completeness follows
from Lemmas A.35 and A.33, and the soundness follows from Corollary A.28 by
the same argument as above.

Let us note that the proof does not assume that the templates involved are
composed of finite structures; nevertheless the finiteness of $\mathbf{A}$ and
$\mathbf{B}$ is useful to ensure that the reductions involved are computable
in polynomial-time. No assumptions on finiteness of $\mathbf{A}^{\prime}$ and
$\mathbf{B}^{\prime}$ are needed either way.

##  Appendix B More on arc-consistency reductions

We start this appendix with another preliminary section recalling more details
of the algebraic approach to promise CSP [6].

###  B.1. Algebraic approach to the promise label cover problem

As we mentioned several times above, the label cover problem and its promise
variant is often used in algebraic reductions between (promise) CSPs. A key
advantage of our typed setting is that we can now express these reductions in
the same language as gadget reductions.

Let us in particular reformulate the problem of _promise satisfaction of minor
conditions_ $\operatorname{PMC}_{\mathscr{M}}$ [6, Definition 3.10] in the
language of promise label cover.131313We note for the reader who is familiar
with the notion of a minor condition, that there is a direction translation
between label cover instances and minor conditions using the following
dictionary: _function symbol_ $f$ of arity $D$ — an _element_ $f$ of type $D$;
an _identity_ $f\approx g^{\pi}$ — a _constraint_ $(f,g)\in E_{\pi}$. This
problem can be expressed as a promise CSP whose template is consists of the
template of label cover $\mathbf{P}$ and a minion $\mathscr{M}$, which is
treated as an infinite structure in the label cover signature as described in
Section 5. The template of the label cover $\mathbf{P}$ (Definition 2.7)
coincides with the minion $\mathscr{P}$ (see Example 5.9), hence we can use
$\mathscr{P}$ instead of $\mathbf{P}$.

######  Definition B.1.

The _promise label cover problem_ assigned to a minion $\mathscr{M}$, denoted
simply as $\operatorname{PCSP}(\mathscr{P},\mathscr{M})$, is the problem whose
input is a label cover instance $\mathbf{S}$, and the goal is to decide
between the cases $\mathbf{S}\to\mathscr{P}$ and
$\mathbf{S}\not\to\mathscr{M}$.

Though the templates in the problem
$\operatorname{PCSP}(\mathscr{P},\mathscr{M})$ are infinite, the instances are
finite. Often it is enough to work with a finite reduct of the signature of
label cover, and hence the structures of the template will become finite
assuming that the minion $\mathscr{M}$ is _locally finite_ , i.e., that
$\mathscr{M}^{(X)}$ is finite for all finite sets $X$ (which is true if
$\mathscr{M}$ is a polymorphism minion of a finite promise template).

In this language, a core theorem of the algebraic approach [6, Theorem 3.12]
states that $\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ and
$\operatorname{PCSP}(\mathscr{P},\mathscr{M})$ are interreducible by gadget
reductions for any promise template $\mathbf{A},\mathbf{B}$ whose polymorphism
minion is $\mathscr{M}$. More precisely, the theorem states the following.

######  Theorem B.2 (Theorem 3.12 of [6]).

Let $\mathbf{A},\mathbf{B}$ be a promise template, and
$\mathscr{M}=\operatorname{Pol}(\mathbf{A},\mathbf{B})$.

  1. (1)

There exists a gadget reduction from
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ to
$\operatorname{PCSP}(\mathscr{P},\mathscr{M})$;

  2. (2)

For every finite reduct $\Sigma$ of the label cover signature, there exists a
gadget reduction from $\operatorname{PCSP}(\mathscr{P},\mathscr{M})$, with the
inputs restricted to $\Sigma$-structures, to
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$.

We note that this statement could be proven as a corollary of Theorem 5.8
since every minion $\mathscr{M}$ is isomorphic to
$\operatorname{Pol}(\mathscr{P},\mathscr{M})$.141414This isomorphism is known
in category theory as the Yoneda Lemma. Let us nevertheless warn the reader
that this ‘alternative’ proof would be cyclic since Barto, Bulín, Krokhin, and
Opršal [6] prove Theorem 5.8 [6, Theorem 3.1] using Theorem B.2 [6, Theorem
3.12].

Let us recall the two reductions used to prove Theorem B.2. The reduction in
item (1) is the universal gadget $\pi_{\mathbf{A}}$, the correctness of this
reduction is proven using the following lemma [6, Lemma 3.16 & Remark 3.17].

######  Lemma B.3.

Let $\mathbf{A},\mathbf{B}$ be a promise template. For all label cover
instances $\mathbf{X}$, $\pi_{\mathbf{A}}(\mathbf{X})\to\mathbf{B}$ if and
only if $\mathbf{X}\to\operatorname{Pol}(\mathbf{A},\mathbf{B})$.

Even though the above lemma is phrased in [6] with the assumption that the
structures $\mathbf{A}$, $\mathbf{B}$, and $\mathbf{X}$ are finite, it holds
for infinite structures as well (though the reduction $\pi_{\mathbf{A}}$
ceases to be polynomial-time computable). In particular, we have that for each
minion $\mathscr{M}$, $\pi_{\mathbf{A}}(\mathscr{M})\to\mathbf{B}$ if and only
if $\mathscr{M}\to\operatorname{Pol}(\mathbf{A},\mathbf{B})$. We note without
a proof that the structure $\pi_{\mathbf{A}}(\mathscr{M})$ is in fact
isomorphic to _free structure_ of $\mathscr{M}$ generated by $\mathbf{A}$,
usually denoted by $\operatorname{{\mathbf{F}}}_{\mathscr{M}}(\mathbf{A})$ [6,
Definition 4.1] (see also [6, Lemma 4.4]).

The other reduction, from $\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ to
$\operatorname{PCSP}(\mathscr{P},\mathscr{M})$, is the reduction
$\rho^{\mathbf{A}}$ which we introduced in Definition 5.2. The following lemma
follows from [6, Lemmas 3.14 & 4.3, and Theorem 4.12].

######  Lemma B.4.

Let $\mathscr{M}$ be a minion, and $\mathbf{A}$, $\mathbf{X}$ be two
structures of the same signature. Then
$\rho^{\mathbf{A}}(\mathbf{X})\to\mathscr{M}$ if and only if
$\mathbf{X}\to\pi_{\mathbf{A}}(\mathscr{M})$.

We note that Theorem B.2 (and consequently Theorem 5.8) can be proven directly
using just Lemmas B.3 and B.4 and Theorem 4.11 of Krokhin, Opršal, Wrochna,
and Živný [38].

###  B.2. Proof of Theorem 5.11

Let $\mathscr{A}=\operatorname{Pol}(\mathbf{A},\mathbf{A}^{\prime})$ and
$\mathscr{B}=\operatorname{Pol}(\mathbf{B},\mathbf{B}^{\prime})$. First, we
show that if there is a minion homomorphism
$\xi\colon\omega(\mathscr{B})\to\mathscr{A}$ then
$\operatorname{PCSP}(\mathbf{A},\mathbf{A}^{\prime})$ reduces to
$\operatorname{PCSP}(\mathbf{B},\mathbf{B}^{\prime})$ via an arc-consistency
reduction. The completeness of the arc-consistency reduction is
straightforward and analogous to the proof of the completeness of the
$k$-consistency reduction (see Lemma A.33). We focus on the soundness. Assume
that
$\pi_{\mathbf{B}}\kappa_{\text{arc}}\sigma^{\mathbf{A}}(\mathbf{X})\to\mathbf{B}^{\prime}$
with the aim to show that $\mathbf{X}\to\mathbf{A}^{\prime}$. First, we have
that $\kappa_{\text{arc}}\sigma^{\mathbf{A}}(\mathbf{X})\to\mathscr{B}$ by
Lemma B.3. Further, $\sigma^{\mathbf{A}}(\mathbf{X})\to\omega(\mathscr{B})$ by
Lemma 5.12, and consequently $\sigma^{\mathbf{A}}(\mathbf{X})\to\mathscr{A}$.
Finally, the latter implies that $\mathbf{X}\to\mathbf{A}^{\prime}$ [6, Lemma
3.14] (or Lemmas B.3 and B.4).

To show the other implication, assume that
$\operatorname{PCSP}(\mathbf{A},\mathbf{A}^{\prime})\mathrel{\leq_{\text{arc-
cons}}}\operatorname{PCSP}(\mathbf{B},\mathbf{B}^{\prime})$, and consider the
structure $\pi_{\mathbf{A}}\omega(\mathscr{B})$.151515This structure is the
_free structure_ of $\omega(\mathscr{B})$ generated by $\mathbf{A}$. To obtain
a minion homomorphism from $\omega(\mathscr{B})$ to $\mathscr{A}$, it is
enough to show that
$\pi_{\mathbf{A}}\omega(\mathscr{B})\to\mathbf{A}^{\prime}$ (Lemma B.3). We
prove this by using the soundness of arc-consistency. Since
$\pi_{\mathbf{A}}\omega(\mathscr{B})$ may be infinite, we may not invoke
soundness directly. This can be dealt with by the standard compactness
argument (see, e.g., [6, Remark 7.13]) — to show that a $\mathbf{F}$ maps
homomorphically to a finite structure $\mathbf{A}^{\prime}$, it is enough to
show that every finite substructure of $\pi_{\mathbf{A}}\omega(\mathscr{B})$
does. For the rest of the proof, we assume that $\mathbf{F}$ is an arbitrary
finite substructure of $\pi_{\mathbf{A}}\omega(\mathscr{B})$. We have that:
$\sigma_{\mathbf{A}}(\mathbf{F})\to\omega(\mathscr{B})$ (Lemma B.4),
$\kappa_{\text{arc}}\sigma_{\mathbf{A}}(\mathbf{F})\to\mathscr{B}$ (Lemma
5.12), and
$\pi_{\mathbf{B}}\kappa_{\text{arc}}\sigma_{\mathbf{A}}(\mathbf{F})\to\mathbf{B}^{\prime}$
(Lemma B.3). Since the last homomorphism witnesses that
$\kappa_{\text{arc}}^{\mathbf{A},\mathbf{B}}(\mathbf{F})$ is not a negative
instance of $\operatorname{PCSP}(\mathbf{B},\mathbf{B}^{\prime})$, we get that
$\mathbf{F}\to\mathbf{A}^{\prime}$ by the soundness of the arc-consistency
reduction as we wanted to show. ∎

We briefly note that the above proof can be adapted for the cases when
$\mathbf{A}$, $\mathbf{A}^{\prime}$, $\mathbf{B}$, and $\mathbf{B}^{\prime}$
are not necessarily finite: The reverse implication (showing that arc-
consistency is a valid reduction) holds unconditionally, though it might not
always give an efficient reduction. The other implication (showing necessity
of a minion homomorphism) uses only finiteness of $\mathbf{A}^{\prime}$.
Alternatively, it can be proven under the assumption that
$\pi_{\mathbf{A}}\omega(\mathscr{B})$ is finite, e.g., if $\mathbf{A}$ is
finite and $\mathscr{B}$ is locally finite.

###  B.3. A sufficient condition for Datalog∪ reductions

We combine Theorem 5.11 with results of Barto and Kozik [9] to provide a new
sufficient condition for the existence of a Datalog∪ reduction. Namely, we can
connect the construction $\omega$ with the notion of _minion
$(d,r)$-homomorphisms_ [9, Definition 5.1].

######  Definition B.5.

A _chain of minors_ in a minion $\mathscr{M}$ of length $r$ is a sequence
$t_{0},\dots,t_{r}\in\mathscr{M}$ together with functions $\pi_{i,j}$ for
$0\leq i<j\leq r$ such that $t_{j}=t_{i}^{\pi_{i,j}}$ and
$\pi_{i,k}=\pi_{j,k}\circ\pi_{i,j}$ for all $i<j<k$.

Let $\mathscr{M}$ and $\mathscr{N}$ be two minions. A _$(d,r)$ -homomorphism_
from $\mathscr{M}$ to $\mathscr{N}$ is a mapping $\xi$ that assigns to each
element of $\mathscr{M}$ a non-empty subset of $\mathscr{N}$ of size at most
$d$ such that

  1. (1)

for all $f\in\mathscr{M}$, every $g\in\xi(f)$ has the same arity as $f$.

  2. (2)

for each chain of minors in $\mathscr{M}$ as above, there exist $i<j$ and
$g_{i}\in\xi(t_{i})$, $g_{j}\in\xi(t_{j})$ such that
$g_{j}=g_{i}^{\pi_{i,j}}$.

######  Corollary B.6.

Assume $\mathbf{A},\mathbf{A}^{\prime}$ and $\mathbf{B},\mathbf{B}^{\prime}$
are two promise templates. If there exist $d,r$ and a minion
$(d,r)$-homomorphism from
$\omega\operatorname{Pol}(\mathbf{B},\mathbf{B}^{\prime})$ to
$\operatorname{Pol}(\mathbf{A},\mathbf{A}^{\prime})$, then
$\operatorname{PCSP}(\mathbf{A},\mathbf{A}^{\prime})\mathrel{\leq_{\text{Datalog}}}\operatorname{PCSP}(\mathbf{B},\mathbf{B}^{\prime})$.

The proof is a combination of the proof of [9, Theorem 5.1] and the proof of
Theorem 5.11. Loosely speaking, we have the following chain of reductions:

$\operatorname{PCSP}(\mathbf{A},\mathbf{A}^{\prime})\mathrel{\leq_{\text{Datalog}}}\operatorname{PCSP}(\mathscr{P},\omega(\mathscr{B}))\mathrel{\leq_{\text{arc-
cons}}}\operatorname{PCSP}(\mathbf{B},\mathbf{B}^{\prime})$

where the Datalog∪ reduction is given by [9, Theorem 5.1]. To make this proof
formal, we need to phrase [9, Theorem 5.1] in the language of Datalog
reductions. This could be done by a careful inspection of the proof.
Nevertheless, we present a complete argument building on the proof of the said
theorem assuming only the Combinatorial Gap Theorem [9, Theorem 2.1]. The core
of the argument remains the same, though the argument is slightly simpler than
in [9] due to the fact that the typed setting is more natural here, as noted
in [7, Appendix B.4].

To formulate the Combinatorial Gap Theorem we need the following technical
definition.

######  Definition B.7.

Let $\mathbf{X}$ be an instance of $\operatorname{CSP}(\mathbf{A})$ we say
that a sequence $(\mathcal{I}_{0},\dots,\mathcal{I}_{r})$ is a  _consistent
sequence of partial solution schemes_ of arities $k_{0}\geq\dots\geq k_{r}$
and a value $d>0$, if

  * •

$\mathcal{I}_{i}$ assigns to each $U\in\binom{X}{\leq k_{i}}$ a set of at most
$d$ partial solutions on $U$, and

  * •

for every $U_{0}\supseteq\dots\supseteq U_{K}$ with $U_{i}\in\binom{X}{\leq
k_{i}}$, there exists $i<j$ such that

$\mathcal{I}_{j}(U_{j})\cap(\mathcal{I}_{i}(U_{i})\circ\iota_{i,j})\neq\emptyset,$

where $\iota_{i,j}\colon U_{j}\hookrightarrow U_{i}$ is the inclusion mapping.

######  Theorem B.8 (Combinatorial Gap Theorem [9]).

For all positive integers $m$, any (possibly infinite) structure $\mathbf{D}$
whose relations are of arity not more than $m$, and $r,d\geq 1$, there exists
a sequence $k_{0}\geq\dots\geq k_{r}$ such that every instance that allows a
consistent sequence of partial solution schemes of arities $k_{0},\dots,k_{r}$
and value $d$ is solvable.

Using the above theorem, we can prove the corollary.

######  Proof B.9 (Proof of Corollary B.6).

Let $k_{0},\dots,k_{r}$ be as in the Combinatorial Gap Theorem for parameters
$d$ and $r$ and template $\mathbf{A}^{\prime}$. We claim that
$\operatorname{PCSP}(\mathbf{A},\mathbf{A}^{\prime})\mathrel{\leq_{k\text{-cons}}}\operatorname{PCSP}(\mathbf{B},\mathbf{B}^{\prime})$
for $k=k_{0}$. As usual, it is enough to prove soundness of the
$k$-consistency reduction. Assume
$\kappa_{k}^{\mathbf{A},\mathbf{B}}(\mathbf{X})\to\mathbf{B}^{\prime}$. Hence
$\pi_{\mathbf{B}}\kappa_{\text{arc}}\sigma_{k}^{\mathbf{A}}(\mathbf{X})\to\mathbf{B}^{\prime}$
which implies that
$\kappa_{\text{arc}}\sigma_{k}^{\mathbf{A}}(\mathbf{X})\to\operatorname{Pol}(\mathbf{B},\mathbf{B}^{\prime})$
(Lemma B.3). Consequently,
$\sigma_{k}^{\mathbf{A}}(\mathbf{X})\to\omega\operatorname{Pol}(\mathbf{B},\mathbf{B}^{\prime})$
by Lemma 5.12. The rest of the proof is a rephrasing of the proof of Barto and
Kozik [9, Theorem 5.1].

We claim that the instance $\mathbf{X}$ of
$\operatorname{CSP}(\mathbf{A}^{\prime})$ allows a consistence sequence of
partial assignment schemes of arities $k_{0}\geq\dots\geq k_{r}$. We let

$\mathcal{I}_{i}(K)=\\{g(\mathcal{F}_{K})\mid g\in\xi(f_{K})\\}$

where $g(\mathcal{F}_{K})\colon K\to\mathbf{A}^{\prime}$ denotes the
component-wise application of $g$ to all the elements of $\mathcal{F}_{K}$.
More precisely, we let $g(\mathcal{F}_{K})\colon x\mapsto g(e_{x})$ for each
$x\in K$ where $e_{x}\colon\mathcal{F}_{K}\to A^{\prime}$ is the evaluation at
$x$, i.e., $e_{x}(f)=f(x)$. Since each $f\in\mathcal{F}_{K}$ is a partial
homomorphism from $K$ to $\mathbf{A}$ and $g$ is a polymorphism,
$g(\mathcal{F}_{K})$ is a partial homomorphism from $K$ to
$\mathbf{A}^{\prime}$. We get the consistency relation from the fact that
$\xi$ is a $(d,r)$-homomorphism: if $K_{0}\supseteq\dots\supseteq K_{r}$, and
$g_{i}\in\xi(f_{K_{i}})$, then for some $i<j$, $g_{i}^{\pi_{i,j}}=g_{j}$ where
$\pi_{i,j}\colon\mathcal{F}_{K_{i}}\to\mathcal{F}_{K_{j}}$ is defined by
$\pi_{i,j}(f)=f|_{K_{j}}$, and hence

$g_{j}(\mathcal{F}_{K_{j}})(x)=g_{j}(e_{x})=g_{i}^{\pi_{i,j}}(e_{x})=g_{i}(e_{x}\circ\pi_{i,j})=g_{i}(e_{x})=g(\mathcal{F}_{K_{j}})(x)$

for all $x\in K_{j}$. Above, we used $e_{x}$ to denote both a function from
$\mathcal{F}_{K_{i}}$ as well as from $\mathcal{F}_{K_{j}}$; we have
$e_{x}(f)=e_{x}(f|_{K_{j}})$ since $x\in K_{j}\subseteq K_{i}$. This concludes
checking that the assumptions of the Combinatorial Gap Theorem are satisfied,
and hence $\mathbf{X}\to\mathbf{A}^{\prime}$, as we wanted.

We note that the condition given in Corollary B.6 is sufficient but not
necessary as is shown in the following example.

######  Example B.10.

We claim that there is no $(d,r)$-homomorphism from $\mathscr{H}$ to
$\operatorname{Pol}(\mathbf{K}_{2})$ for any $d,r\geq 1$ while
$\operatorname{CSP}(\mathbf{K}_{2})$ reduces to the trivial problem by the
$3$-consistency reduction (as shown in Example 3.7).

The key observation is that $\operatorname{Pol}(\mathbf{K}_{2})$ contains no
$f$ that satisfies $f^{\pi}=f$ for a permutation $\pi$ of order two without
fixed points (i.e., with only cycles of length 2), while $\mathscr{H}$
contains an $f$ that satisfies $f^{\pi}=f$ for all such permutations on any
fixed set. We use this $f\in\mathscr{H}$ to build a long chain of minors, and
consequently force that some of the $d$ elements in the image of some
$(d,r)$-homomorphisms satisfy $c_{1}^{\pi}=c_{2}$. If we manage to force
enough of these relations, we will obtain a $c\in\chi(f)$ with $c^{\pi}=c$
which will yield a contradiction.

Fix $d$ and $r$, and let $n\geq(r+1)d$. We start with constructing a
permutation group where all elements are of order two and have no fixed
points. For that, we take the Cayley representation of $\mathbb{Z}_{2}^{n}$ —
i.e., let $\mathbb{Z}_{2}^{n}$ act on its base set $N=\\{0,1\\}^{n}$ by left
multiplication. We denote this permutation group by $\mathbb{G}$.

Now let $f\in\mathscr{H}^{(N)}$ be an element satisfying $f^{\pi}=f$ for all
$\pi\in\mathbb{G}$, i.e., $f=N$. To construct a chain of minor we need to fix
$\pi_{i,j}\in\mathbb{G}$ such that $\pi_{j,k}\circ\pi_{i,j}=\pi_{i,k}$. We
pick $\epsilon_{0},\dots,\epsilon_{k-1}$ to be elements in $\mathbb{G}$
corresponding to a vector-space basis of $\mathbb{Z}_{2}^{k}$, and note that
the product of $\prod_{i\in I}\epsilon_{i}$ is non-trivial for all
$I\neq\emptyset$. Now, we can let

$\pi_{i,j}=\prod_{\ell=i+1}^{j}\epsilon_{\ell}.$

Indeed, we have that $f^{\pi_{i,j}}=f$, for all $i<j$, hence $f$ itself
creates a chain of minors of length $(r+1)d$.

Assume that $\chi\colon\mathscr{H}\to\operatorname{Pol}(\mathbf{K}_{2})$ is a
$(d,r)$-homomorphism. We consider a labelled graph $E$ with vertices $\chi(f)$
defined as follows: two vertices $u,v$ are connected by an edge labelled by a
non-trivial element $\pi\in\mathbb{G}$ if $u^{\pi}=v$ (note that since $\pi$
is of order two, this condition is equivalent to $u=v^{\pi}$, hence the edges
are unoriented). We use the long chain of minors to force edges into this
graph to obtain a cycle: For all $k<d$, there exist $i,j$ with $(r+1)k\leq
i<j<(r+1)(k+1)$ such that

$\chi(f)^{\pi_{i,j}}\cap\chi(f^{\pi_{i,j}})\neq\emptyset.$

Since $f^{\pi_{i,j}}=f$, this forces an edge into $E$ labelled by $\pi_{i,j}$.
Hence the graph has at least $d$ edges. Moreover observe that any product of a
subset of the labels of these edges is non-trivial. Since we have at least $d$
edges and only $d$ vertices, there is a cycle in $E$. Let $c_{0},\dots,c_{k}$
be such a cycle with labels $\lambda_{0}$, $\lambda_{1}$, etc. We claim that
$c_{0}^{\pi}=c_{0}$ where $\pi$ is the product of all the labels of edges of
the cycle. By induction, we get

$c_{i+1}^{\prod_{j\leq
i}\lambda_{j}}=(c_{i+1}^{\lambda_{i}})^{\prod_{j<i}\lambda_{j}}=c_{i}^{\prod_{j<i}\lambda_{j}}=c_{0}$

where $c_{k+1}=c_{0}$. Since $\pi=\prod_{i\leq k}\lambda_{i}$ is non-trivial,
we get that $c_{0}^{\pi}=c_{0}$ is in contradiction with $c_{0}$ being a
polymorphism of $\mathbf{K}_{2}$.

Finally, let us note to the reader who is familiar with the reduction used in
[9], described as _$k$ -reduction_ in [37, Section 4.2], that
$\operatorname{CSP}(\mathbf{K}_{2})$ reduces to Horn-3SAT by 3-reduction,
hence $(d,r)$-homomorphisms are not even necessary for this $k$-reduction.

###  B.4. Arc-consistency reductions are transitive

We argue that arc-consistency reductions compose by using the language of
category theory that is incredibly elegant for this purpose. Essentially, this
claim follows from an observation that $\omega$ is a _comonad_ , and Theorem
5.11 which characterises the arc-consistency reduction in terms of _co-Kleisli
arrows_ of this comonad. Let us briefly outline the definitions. Although it
is not the traditional way, we define these notions together to highlight
their connection.

######  Definition B.11.

Assume $\eta$ is an endofunctor of some category, and $A,B$ are two objects. A
_co-Kleisli arrow_ is a morphism $f\colon\eta(A)\to B$.161616Usually, a
morphism $\eta(A)\to B$ is called a co-Kleisli arrow only if $\eta$ is a
comonad, and in that case the ‘co-’ prefix is often dropped since its implied.
A functor $\eta$ is a _comonad_ if its co-Kleisli arrows form a category with
the same objects as the underlying category, i.e., if there is an associative
binary operator $\circ_{\eta}$ that assigns to every pair of co-Kleisli arrows
$f\colon\eta(A)\to B$ and $g\colon\eta(B)\to C$ a co-Kleisli arrow
$g\mathbin{\circ_{\eta}}f\colon\eta(A)\to C$, and for each object $A$, there
is a co-Kleisli arrow $\nu^{A}\colon\eta(A)\to A$ that acts as the identity
w.r.t. $\circ_{\eta}$.

######  Lemma B.12.

$\omega$ is a comonad.

######  Proof B.13.

The unit $\nu^{\mathscr{M}}$ is the map
$\nu\colon\omega(\mathscr{M})\to\mathscr{M}$ we mentioned above, i.e.,
$\nu^{\mathscr{M}}_{X}(Y,f)=f^{\iota}$ where $\iota\colon Y\hookrightarrow X$
is the inclusion mapping. To define the composition, it is easier to show how
to get from a co-Kleisli arrow $\xi\colon\omega(\mathscr{M})\to\mathscr{N}$ a
minion homomorphism
$\xi^{\sharp}\colon\omega(\mathscr{M})\to\omega(\mathscr{N})$; this
$\xi^{\sharp}$ is defined by $\xi_{Y}^{\sharp}(X,f)=(X,\xi_{X}(X,f))$ where
$Y\supseteq X$ and $f\in\mathscr{M}^{(X)}$. The composition is then defined as

$\xi\circ_{\omega}\zeta=\xi\circ\zeta^{\sharp}.$

Checking that $\circ_{\omega}$ is associative and that $\nu^{\mathscr{M}}$ is
the identity element of $\circ_{\omega}$ is straightforward.

Remark that, in the above proof, we showed that
$\omega(\mathscr{M})\to\omega(\mathscr{N})$ if and only if
$\omega(\mathscr{M})\to\mathscr{N}$. Finally, as an easy corollary of the
above lemma and the fact that co-Kleisli arrows of a comonad compose, we get
that arc-consistency reductions are transitive.

######  Corollary B.14.

If
$\operatorname{PCSP}(\mathbf{A},\mathbf{A}^{\prime})\mathrel{\leq_{\text{arc-
cons}}}\operatorname{PCSP}(\mathbf{B},\mathbf{B}^{\prime})$ and
$\operatorname{PCSP}(\mathbf{B},\mathbf{B}^{\prime})\mathrel{\leq_{\text{arc-
cons}}}\operatorname{PCSP}(\mathbf{C},\mathbf{C}^{\prime})$, then
$\operatorname{PCSP}(\mathbf{A},\mathbf{A}^{\prime})\mathrel{\leq_{\text{arc-
cons}}}\operatorname{PCSP}(\mathbf{C},\mathbf{C}^{\prime})$.

##  Appendix C Sherali-Adams is a $k$-consistency reduction to linear
programming

In this appendix, we provide a detailed proof of the fact that Sherali-Adams
hierarchy coincides with the $k$-consistency hierarchy of linear programming.
The proof is a comparison of Sherali-Adams understood as a reduction to linear
programming and the $k$-consistency reduction. It requires two key properties
of linear programming, and its polymorphisms: firstly, that the linear system
produced by the Sherali-Adams is as good as the universal gadget, and
secondly, that the polymorphisms of linear programming allow a homomorphism
$\operatorname{Pol}(\mathbf{Q}_{\text{conv}})\to\omega\operatorname{Pol}(\mathbf{Q}_{\text{conv}})$.

Let us start with recalling a description of the polymorphism minion of linear
programming, see also [6, Section 7.2]. The minion
$\operatorname{Pol}(\mathbf{Q}_{\text{conv}})$ is isomorphic to the minion
$\mathscr{Q}_{\text{conv}}$ described as follows:
$\mathscr{Q}_{\text{conv}}^{(X)}$ consists of all rational probability
distributions $\lambda$ on $X$, i.e., $\lambda\colon X\to\mathbb{Q}$ with
$\sum_{x\in X}\lambda(x)=1$ and $\lambda(x)\geq 0$ for all $x\in X$, and for
$\pi\colon X\to Y$, we let $\lambda^{\pi}$ be the probability distribution of
$\pi(x)$ when $x$ is sampled according to $\lambda$, i.e.,
$\lambda^{\pi}(x)=\sum_{y\in\pi^{-1}(x)}\lambda(y)$.

######  Lemma C.1.

The minions $\operatorname{Pol}(\mathbf{Q}_{\text{conv}})$ and
$\mathscr{Q}_{\text{conv}}$ are isomorphic.

######  Proof C.2.

The key observation is that every polymorphism of $\mathbf{Q}_{\text{conv}}$
is of the form

$f(x_{1},\dots,x_{n})=\sum_{i=1}^{n}\lambda_{i}x_{i}$

for some $\lambda_{1},\dots,\lambda_{n}\geq 0$ such that
$\sum_{i=1}^{n}\lambda_{i}=1$. Identifying such polymorphism with the
probability distribution $\lambda\colon i\mapsto\lambda_{i}$ then yields the
required isomorphism. It is not hard to check that minors are indeed taken
accordingly.

The above isomorphism is implicitly used in characterisation of (promise) CSPs
solved by the _basic linear programming relaxation_ of CSPs [6, Theorem 7.9].
This basic linear programming relaxation of $\operatorname{CSP}(\mathbf{A})$
can be described as a composition
$\lambda_{\text{conv}}\circ\rho^{\mathbf{A}}$, where $\lambda_{\text{conv}}$
is a gadget that produces from label cover instances to linear programs (i.e.,
structures similar to $\mathbf{Q}_{\text{conv}}$). It is the same construction
as in step (S2) of the Sherali-Adams relaxation. For simplicity, we treat the
output of $\lambda_{\text{conv}}$ as a linear program rather than a structure
with the same signature as $\mathbf{Q}_{\text{conv}}$.

######  Definition C.3.

Let $\mathbf{S}$ be a label cover instance,
$\lambda_{\text{conv}}(\mathbf{S})$ is the following linear program with
variables $x_{s,i}$ for each type $X$, $s\in S_{X}$, and $i\in X$:

$\displaystyle\sum_{i\in X}x_{s,i}$ $\displaystyle=0$ for all $s\in\mathbf{S}$
of type $X$, (C.1) $\displaystyle\sum_{i\in\pi^{-1}(j)}x_{s,i}$
$\displaystyle=x_{t,j}$ for all $\pi\colon X\to Y$, $(s,t)\in
E_{\pi}^{\mathbf{S}}$, and $j\in Y$. (C.2)

It is not hard to check that $\lambda_{\text{conv}}$ can be described as a
gadget replacement, and that the $k$-th level of the Sherali-Adams relaxation
of an instance $\mathbf{X}$ of $\operatorname{CSP}(\mathbf{A})$ can be
described as $\lambda_{\text{conv}}\sigma_{k}^{\mathbf{A}}(\mathbf{X})$.
Recall that $\sigma_{k}^{\mathbf{A}}(\mathbf{X})$ denotes the label cover
instance obtained from an instance $\mathbf{X}$ of
$\operatorname{CSP}(\mathbf{A})$ by performing only steps (C1) and (C4) in the
$k$-consistency enforcement, i.e., the label cover instance constructed in
step (S1) of the Sherali-Adams relaxation.

The important property of $\lambda_{\text{conv}}$ is that it is ‘as good as
the universal gadget’, i.e., that we can freely exchange
$\lambda_{\text{conv}}$ and the universal gadget
$\pi_{\mathbf{Q}_{\text{conv}}}$. We informally call this fact the _short code
property_ of linear programming.171717The gadget $\lambda_{\text{conv}}$ is a
shorter alternative to the universal gadget which is the natural _long code
test_ for linear programming, hence the name.

######  Lemma C.4.

For every label cover instance $\mathbf{X}$,
$\lambda_{\text{conv}}(\mathbf{X})\to\mathbf{Q}_{\text{conv}}$ if and only if
$\pi_{\mathbf{Q}_{\text{conv}}}(\mathbf{X})\to\mathbf{Q}_{\text{conv}}$.

######  Proof C.5.

Observe that $\lambda_{\text{conv}}(\mathbf{X})\to\mathbf{Q}_{\text{conv}}$ if
and only if $\mathbf{X}$ is satisfied in $\mathscr{Q}_{\text{conv}}$: the
assignment $\lambda_{s}(i)=x_{s,i}$ gives the required probability
distributions given that $x_{s,i}$ is a solution to
$\lambda_{\text{conv}}(\mathbf{X})$, and vice-versa. We also have that
$\pi_{\mathbf{Q}_{\text{conv}}}(\mathbf{X})\to\mathbf{Q}_{\text{conv}}$ if and
only if $\mathbf{X}$ is satisfied in
$\operatorname{Pol}(\mathbf{Q}_{\text{conv}})$ (Lemma B.3). Hence the
statement follows from the isomorphism of the two minions (Lemma C.1).

We turn our attention to the minion $\mathscr{Q}_{\text{conv}}$. The following
lemma implies that a (promise) CSP is reducible to linear programming by the
arc-consistency reduction if and only if it is solved by the basic linear
programming relaxation, i.e., the step enforcing consistency in the reduction
can be skipped without any harm.

######  Lemma C.6.

There is a minion homomorphism

$\mathscr{Q}_{\text{conv}}\to\omega(\mathscr{Q}_{\text{conv}}).$

######  Proof C.7.

We define a minion homomorphism
$\xi\colon\mathscr{Q}_{\text{conv}}\to\omega(\mathscr{Q}_{\text{conv}})$ by

$\xi(\lambda)=(\operatorname{supp}(\lambda),\lambda|_{\operatorname{supp}(\lambda)})$

where $\operatorname{supp}(\lambda)$ is the set of all values $x\in X$ that
have a non-zero probability in $\lambda$.

Checking that $\xi$ is a minion homomorphism is straightforward: First,
observe that
$\operatorname{supp}(\lambda^{\pi})=\pi(\operatorname{supp}(\lambda))$ since
$y$ has a non-zero probability according to $\lambda^{\pi}$ if only if there
is $x$ with a non-zero probability in $\lambda$ such that $\pi(x)=y$. Further
we have that

$\lambda^{\pi}|_{\operatorname{supp}(\lambda^{\pi})}=(\lambda|_{\operatorname{supp}(\lambda)})^{\pi|_{\operatorname{supp}(\lambda)}}$

since both are probability distributions of $\pi(x)$ when $x$ is sampled
according to $\lambda$.

Let us now prove Theorem 4.5.

######  Proof C.8 (Proof of Theorem 4.5).

We prove the theorem by the comparison of the two reductions. Sherali-Adams
accepts if and only if

$\lambda_{\text{conv}}\sigma_{k}^{\mathbf{A}}(\mathbf{X})\to\mathbf{Q}_{\text{conv}}.$
(C.3)

Compare this to when the $k$-consistency reduction to
$\operatorname{CSP}(\mathbf{Q}_{\text{conv}})$ accepts, which is if and only
if

$\pi_{\mathbf{Q}_{\text{conv}}}\kappa_{\text{arc}}\sigma_{k}^{\mathbf{A}}(\mathbf{X})\to\mathbf{Q}_{\text{conv}}.$
(C.4)

By Lemma C.4, the condition (C.3) is equivalent to
$\sigma_{k}^{\mathbf{A}}(\mathbf{X})\to\mathscr{Q}_{\text{conv}}$ which is
equivalent to
$\kappa_{\text{arc}}\sigma_{k}^{\mathbf{A}}(\mathbf{X})\to\mathscr{Q}_{\text{conv}}$
by Lemmas C.6 and 5.12. The latter is equivalent to
$\lambda_{\text{conv}}\kappa_{\text{arc}}\sigma_{k}^{\mathbf{A}}(\mathbf{X})\to\mathbf{Q}_{\text{conv}}$
which is equivalent to the condition (C.4) by Lemma C.4.

Intuitively, the proof claims that the two gadgets are equivalent, and that
the step enforcing arc-consistency can be omitted since linear programming can
emulate arc-consistency. The latter is a general property of promise CSPs
whose polymorphism minion $\mathscr{M}$ admits a homomorphism
$\mathscr{M}\to\omega(\mathscr{M})$, and hence the theorem and its proof can
be generalised for several other hierarchies including a hierarchy that
interweaves with the Lasserre hierarchy.

###  C.1. On tensor hierarchies

Finally, let us briefly comment on a comparison of our hierarchies to those of
Ciardo and Živný [22]. These hierarchies are parametrised by a minion rather
than a promise CSP, and moreover the paper deals only with single-sorted
structures. Let us therefore for this section fix a template
$\mathbf{A},\mathbf{A}^{\prime}$ whose signature contains only one type, and a
minion $\mathscr{M}$. We restate the original definition of Ciardo and Živný
[22] first as stated (without giving all the definition for which we refer to
the cited paper), and then using the language of this paper.

######  Definition C.9 (Ciardo-Živný $k$-th tensor test).

Let $\mathscr{M}$ be a minion, $k\geq 1$. Assuming that $\mathbf{A}$ and
$\mathbf{X}$ are $k$-enhanced structures in the same signature, the $k$-th
tensor test of $\mathscr{M}$ accepts if $\mathbf{X}^{\otimes
k}\to\mathbf{F}_{\mathscr{M}}(\mathbf{A}^{\otimes k})$, and rejects otherwise.

Instead of going through the definitions of the terms used above, let us
paraphrase the test in the language of this paper. First, we will use the
structure $\pi_{\mathbf{B}}(\mathscr{M})$ instead of the free structure
$\mathbf{F}_{\mathscr{M}}(\mathbf{B})$. As we noted before, these structures
are isomorphic. Their homomorphic equivalence, which is enough for our use,
follows directly from Lemma B.4 and [6, Lemma 4.11]). Second, we describe the
$k$-th tensor power together with the operation of $k$-enhancing a structure
as a Datalog interpretation in the following definition.

######  Definition C.10.

Fix $k\geq 1$, and assume that the signature of $\mathbf{A}$ is $\Sigma$. We
define a new signature $\Sigma_{k}$ as follows: it has a single type, a
relational symbol $R_{k}$ of arity $m^{k}$ for each $\Sigma$-symbol $R$ of
arity $m$, and a new relational symbol $T$ of arity $k^{k}$. The domain is
defined by the Datalog program $\tau^{k}_{D}$ with the rule

$D(x_{1},\dots,x_{k})\leftarrow x_{1}=x_{1},\dots,x_{k}=x_{k}.$

The relations $R_{k}$ are defined by the Datalog program $\tau^{k}_{R_{k}}$
with the rule

$R_{k}(x_{e_{m}(1)},\dots,x_{e_{m}(km^{k})})\leftarrow R(x_{1},\dots,x_{m})$

where $e_{m}$ is a function $e_{m}\colon[k]\times[m]^{k}\to[m]$ defined by
$e(i,f)=f(i)$ and we identify the set $[km^{k}]$ with $[k]\times[m]^{k}$ by
ordering the latter lexicographically. And finally, $T$ is defined by a
program $\tau^{k}_{T}$ with the rule

$T(x_{e_{k}(1)},\dots,x_{e_{k}(k^{k+1})})\leftarrow
x_{1}=x_{1},\dots,x_{k}=x_{k}$

where $e_{k}\colon[k^{k+1}]\to[k]$ is as above.

Note that the width of $\tau^{k}$ is the maximum of $k$ and $m$ where $m$
ranges through arities of $\Sigma$-symbols. The $k$-th _tensor test_ is then
defined as follows.

######  Definition C.11 ($k$-th tensor test).

The $k$-th tensor test of a minion $\mathscr{M}$ accepts an instance
$\mathbf{X}$ of $\operatorname{CSP}(\mathbf{A})$ if
$\tau^{k}(\mathbf{X})\to\pi_{\tau^{k}(\mathbf{A})}(\mathscr{M})$, and rejects
otherwise.

Using Lemma B.4, it is easy to observe that the test correctly solves
$\operatorname{PCSP}(\mathbf{A},\mathbf{A}^{\prime})$ if and only if
$\rho^{\tau^{k}(\mathbf{A})}\tau^{k}$ is a valid reduction from
$\operatorname{PCSP}(\mathbf{A},\mathbf{A}^{\prime})$ to
$\operatorname{PCSP}(\mathscr{P},\mathscr{M})$. As a simple corollary of
Theorem 3.18, we get that this reduction is covered by the $k$-consistency
reduction, assuming that $k\geq m$ where $m$ is the maximal arity of relations
of $\mathbf{A}$.

######  Corollary C.12.

Let $\mathbf{A},\mathbf{A}^{\prime}$ be a promise template, $k\geq m$ where
$m$ is the maximal arity of relations in $\mathbf{A}$, and $\mathscr{M}$ be a
minion. If $\operatorname{PCSP}(\mathbf{A},\mathbf{A}^{\prime})$ is correctly
solved by the $k$-th tensor test of $\mathscr{M}$, then it reduces to
$\operatorname{PCSP}(\mathscr{P},\mathscr{M})$ by the $k$-consistency
reduction.

######  Proof C.13.

The tensor test accepts if and only if

$\rho^{\tau^{k}(\mathbf{A})}\tau^{k}(\mathbf{X})\to\mathscr{M}.$

We also have that if $\mathbf{X}\to\mathbf{A}$, then
$\tau^{k}(\mathbf{X})\to\tau^{k}(\mathbf{A})$ and
$\rho^{\tau^{k}(\mathbf{A})}\tau^{k}(\mathbf{X})\to\mathscr{P}$. This means
that if the test correctly solves the promise CSP, then
$\rho^{\tau^{k}(\mathbf{A})}\circ\tau^{k}$ is a valid reduction from
$\operatorname{PCSP}(\mathbf{A},\mathbf{A}^{\prime})$ to
$\operatorname{PCSP}(\mathscr{P},\mathscr{M})$. Since
$\rho^{\tau^{k}(\mathbf{A})}$ is expressible as a gadget replacement and
$\tau^{k}$ is a Datalog interpretation of width $k$, we get the required by
Theorem 3.18.

The converse can be proved under the assumption that
$\mathscr{M}\to\omega(\mathscr{M})$ using the method of the previous
subsection combined with a direct generalisation of an argument in [22] which
shows that if a minion is _conic_ then the $k$-th tensor test is able to find
local homomorphisms on subsets of sizes at most $k$.

### Acknowledgements

A part of this paper is based on a part of an unpublished note by Marcin
Wrochna [46] which contains the characterisation of the arc-consistency
reduction and several observations and statements that served as a ground for
research presented in this paper. We are grateful to Marcin for allowing us to
publish his results among ours. The second author would also like to thank
Anuj Dawar, Joanna Ochremiak, Adam Ó Conghaile, and Antoine Mottet for
inspiring discussions.

## References

  * [1]
  * Arora and Safra [1998] Sanjeev Arora and Shmuel Safra. 1998.  Probabilistic Checking of Proofs: A New Characterization of NP.  _J. ACM_ 45, 1 (1998), 70–122.  https://doi.org/10.1145/273865.273901
  * Atserias, Bulatov, and Dawar [2009] Albert Atserias, Andrei A. Bulatov, and Anuj Dawar. 2009\.  Affine systems of equations and counting infinitary logic.  _Theor. Comput. Sci._ 410, 18 (2009), 1666–1683.  https://doi.org/10.1016/j.tcs.2008.12.049
  * Austrin, Guruswami, and Håstad [2017] Per Austrin, Venkatesan Guruswami, and Johan Håstad. 2017\.  (2+$\epsilon$)-Sat Is NP-hard.  _SIAM Jounal on Computing_ 46, 5 (2017), 1554–1573.  https://doi.org/10.1137/15M1006507
  * Barto, Battistelli, and Berg [2021] Libor Barto, Diego Battistelli, and Kevin M. Berg. 2021\.  Symmetric Promise Constraint Satisfaction Problems: Beyond the Boolean Case. In _38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021_ _(LIPIcs, Vol. 187)_. Schloss Dagstuhl – LZI, Saarbrücken, Germany, 10:1–10:16.  https://doi.org/10.4230/LIPIcs.STACS.2021.10 arXiv:2010.04623
  * Barto, Bulín, Krokhin, and Opršal [2021] Libor Barto, Jakub Bulín, Andrei Krokhin, and Jakub Opršal. 2021.  Algebraic Approach to Promise Constraint Satisfaction.  _J. ACM_ 68, 4 (2021), 28:1–66.  https://doi.org/10.1145/3457606
  * Barto and Butti [2022] Libor Barto and Silvia Butti. 2022.  Weisfeiler-Leman Invariant Promise Valued CSPs. In _28th International Conference on Principles and Practice of Constraint Programming, CP 2022, July 31 to August 8, 2022, Haifa, Israel_ _(LIPIcs, Vol. 235)_. Schloss Dagstuhl – LZI, 4:1–4:17.  https://doi.org/10.4230/LIPIcs.CP.2022.4
  * Barto and Kozik [2014] Libor Barto and Marcin Kozik. 2014.  Constraint Satisfaction Problems Solvable by Local Consistency Methods.  _J. ACM_ 61, 1 (2014).  https://doi.org/10.1145/2556646
  * Barto and Kozik [2022] Libor Barto and Marcin Kozik. 2022.  Combinatorial Gap Theorem and Reductions between Promise CSPs. In _Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)_. SIAM, Virtual Conference, 1204–1220.  https://doi.org/10.1137/1.9781611977073.50
  * Barto, Krokhin, and Willard [2017] Libor Barto, Andrei Krokhin, and Ross Willard. 2017\.  Polymorphisms, and How to Use Them.  In _The Constraint Satisfaction Problem: Complexity and Approximability_ , Andrei Krokhin and Stanislav Živný (Eds.). Dagstuhl Follow-Ups, Vol. 7. Schloss Dagstuhl – LZI, Dagstuhl, Germany, 1–44.  https://doi.org/10.4230/DFU.Vol7.15301.1
  * Barto, Opršal, and Pinsker [2018] Libor Barto, Jakub Opršal, and Michael Pinsker. 2018\.  The wonderland of reflections.  _Israel Journal of Mathematics_ 223, 1 (2018), 363–398.  https://doi.org/10.1007/s11856-017-1621-9
  * Bodirsky and Vucaj [2020] Manuel Bodirsky and Albert Vucaj. 2020.  Two-element structures modulo primitive positive constructability.  _Algebra universalis_ 81, 2 (2020), 1–17.
  * Brakensiek and Guruswami [2021] Joshua Brakensiek and Venkatesan Guruswami. 2021.  Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy.  _SIAM Jounal on Computing_ 50, 6 (2021), 1663–1700.  https://doi.org/10.1137/19M128212X
  * Brakensiek, Guruswami, Wrochna, and Živný [2020] Joshua Brakensiek, Venkatesan Guruswami, Marcin Wrochna, and Stanislav Živný. 2020\.  The Power of the Combined Basic Linear Programming and Affine Relaxation for Promise Constraint Satisfaction Problems.  _SIAM J. Comput._ 49, 6 (2020), 1232–1248.  https://doi.org/10.1137/20M1312745
  * Brandts, Wrochna, and Živný [2021] Alex Brandts, Marcin Wrochna, and Stanislav Živný. 2021\.  The Complexity of Promise SAT on Non-Boolean Domains.  _ACM Trans. Comput. Theory_ 13, 4 (2021).  https://doi.org/10.1145/3470867
  * Bulatov, Jeavons, and Krokhin [2005] Andrei Bulatov, Peter Jeavons, and Andrei Krokhin. 2005\.  Classifying the Complexity of Constraints using Finite Algebras.  _SIAM J. Comput._ 34, 3 (2005), 720–742.  https://doi.org/10.1137/S0097539700376676
  * Bulatov [2017] Andrei A. Bulatov. 2017\.  A Dichotomy Theorem for Nonuniform CSPs. In _2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)_. IEEE, Berkeley, CA, USA, 319–330.  https://doi.org/10.1109/FOCS.2017.37
  * Bulatov and Jeavons [2003] Andrei A. Bulatov and Peter Jeavons. 2003.  An Algebraic Approach to Multi-sorted Constraints. In _Principles and Practice of Constraint Programming – CP 2003, 9th International Conference, CP 2003, Kinsale, Ireland, September 29 – October 3, 2003, Proceedings_ _(Lecture Notes in Computer Science, Vol. 2833)_ , Francesca Rossi (Ed.). Springer, 183–198.  https://doi.org/10.1007/978-3-540-45193-8_13
  * Butti and Dalmau [2021] Silvia Butti and Victor Dalmau. 2021.  The Complexity of the Distributed Constraint Satisfaction Problem. In _38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021, March 16-19, 2021, Saarbrücken, Germany_ _(LIPIcs, Vol. 187)_. Schloss Dagstuhl – LZI, 20:1–20:18.  https://doi.org/10.4230/LIPIcs.STACS.2021.20
  * Ciardo and Živný [2022] Lorenzo Ciardo and Stanislav Živný. 2022\.  CLAP: A New Algorithm for Promise CSPs. In _Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)_. 1057–1068.  https://doi.org/10.1137/1.9781611977073.46
  * Ciardo and Živný [2023] Lorenzo Ciardo and Stanislav Živný. 2023\.  Approximate Graph Colouring and the Hollow Shadow. In _Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20–23, 2023_. ACM, 623–631.  https://doi.org/10.1145/3564246.3585112 arXiv:2211.03168
  * Ciardo and Živný [2023] Lorenzo Ciardo and Stanislav Živný. 2023\.  Hierarchies of Minion Tests for PCSPs through Tensors. In _Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023_. SIAM, 568–580.  https://doi.org/10.1137/1.9781611977554.ch25 arXiv:2207.02277
  * Dawar [2022] Anuj Dawar. 2022\.  Personal communication. (March 2022).  Cambridge, UK.
  * Dinur, Regev, and Smyth [2005] Irit Dinur, Oded Regev, and Clifford Smyth. 2005.  The Hardness of 3-Uniform Hypergraph Coloring.  _Combinatorica_ 25, 5 (2005), 519–535.  https://doi.org/10.1007/s00493-005-0032-4
  * Egri, Larose, and Tesson [2007] László Egri, Benoît Larose, and Pascal Tesson. 2007.  Symmetric Datalog and Constraint Satisfaction Problems in Logspace. In _22nd IEEE Symposium on Logic in Computer Science (LICS 2007), 10-12 July 2007, Wroclaw, Poland, Proceedings_. IEEE Computer Society, 193–202.  https://doi.org/10.1109/LICS.2007.47
  * Feder and Vardi [1998] Tomás Feder and Moshe Y. Vardi. 1998.  The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study Through Datalog and Group Theory.  _SIAM J. Comput._ 28, 1 (1998), 57–104.  https://doi.org/10.1137/S0097539794266766
  * Ficak, Kozik, Olšák, and Stankiewicz [2019] Miron Ficak, Marcin Kozik, Miroslav Olšák, and Szymon Stankiewicz. 2019.  Dichotomy for symmetric Boolean PCSPs. In _Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP’19)_ _(LIPIcs, Vol. 132)_. Schloss Dagstuhl – LZI, Wadern, 57:1–12.  https://doi.org/10.4230/LIPIcs.ICALP.2019.57
  * Goldmann and Russell [2002] Mikael Goldmann and Alexander Russell. 2002.  The Complexity of Solving Equations over Finite Groups.  _Information and Computation_ 178, 1 (2002), 253–262.  https://doi.org/10.1006/inco.2002.3173
  * Guruswami and Sandeep [2020] Venkatesan Guruswami and Sai Sandeep. 2020.  $d$-To-1 Hardness of Coloring 3-Colorable Graphs with ${O}(1)$ Colors. In _47th International Colloquium on Automata, Languages, and Programming, ICALP 2020_ _(LIPIcs)_. Schloss Dagstuhl–LZI, Dagstuhl, Germany, 62:1–62:12.  https://doi.org/10.4230/LIPIcs.ICALP.2020.62
  * Holm [2011] Bjarki Holm. 2011\.  _Descriptive complexity of linear algebra_.  Ph. D. Dissertation. University of Cambridge, UK.  http://bjarkiholm.com/publications/Holm_2010_phd-thesis.pdf
  * Huang [2013] Sangxia Huang. 2013\.  Improved Hardness of Approximating Chromatic Number. In _Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. APPROX/RANDOM 2013_ (Berkeley, CA, USA) _(Lecture Notes in Computer Science, Vol. 8096)_. Springer, 233–243.  https://doi.org/10.1007/978-3-642-40328-6_17
  * Jeavons, Cohen, and Gyssens [1997] Peter Jeavons, David A. Cohen, and Marc Gyssens. 1997\.  Closure properties of constraints.  _J. ACM_ 44, 4 (1997), 527–548.  https://doi.org/10.1145/263867.263489
  * Kazda [2018] Alexandr Kazda. 2018\.  $n$-permutability and linear Datalog implies symmetric Datalog.  _Log. Methods Comput. Sci._ 14, 2 (2018).  https://doi.org/10.23638/LMCS-14(2:3)2018 arXiv:1508.05766
  * Kolaitis and Vardi [1995] Phokion G. Kolaitis and Moshe Y. Vardi. 1995.  On the Expressive Power of Datalog: Tools and a Case Study.  _J. Comput. System Sci._ 51, 1 (1995), 110–134.  https://doi.org/10.1006/jcss.1995.1055
  * Kolaitis and Vardi [2000] Phokion G. Kolaitis and Moshe Y. Vardi. 2000.  Conjunctive-Query Containment and Constraint Satisfaction.  _J. Comput. System Sci._ 61, 2 (2000), 302–332.  https://doi.org/10.1006/jcss.2000.1713
  * Krokhin and Opršal [2019] Andrei Krokhin and Jakub Opršal. 2019.  The complexity of 3-colouring $H$-colourable graphs. In _2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS’19)_. IEEE, Baltimore, MD, USA, 1227–1239.  https://doi.org/10.1109/FOCS.2019.00076
  * Krokhin and Opršal [2022] Andrei Krokhin and Jakub Opršal. 2022.  An invitation to the promise constraint satisfaction problem.  _ACM SIGLOG News_ 9, 3 (2022), 30–59.  https://doi.org/10.1145/3559736.3559740 arXiv:2208.13538
  * Krokhin, Opršal, Wrochna, and Živný [2023] Andrei A. Krokhin, Jakub Opršal, Marcin Wrochna, and Stanislav Živný. 2023\.  Topology and adjunction in promise constraint satisfaction.  _SIAM J. Comput._ 52, 1 (2023), 38–79.  https://doi.org/10.1137/20M1378223 arXiv:2003.11351
  * Larose and Zádori [2007] Benoit Larose and László Zádori. 2007\.  Bounded width problems and algebras.  _Algebra universalis_ 56, 3 (2007), 439–466.  https://doi.org/10.1007/s00012-007-2012-6
  * Nakajima and Živný [2022] Tamio-Vesa Nakajima and Stanislav Živný. 2022\.  Boolean symmetric vs. functional PCSP dichotomy.  (2022).  https://doi.org/10.48550/arXiv.2210.03343 arXiv:2210.03343  Accepted to LICS 2023.
  * Ó Conghaile [2022] Adam Ó Conghaile. 2022\.  Cohomology in Constraint Satisfaction and Structure Isomorphism. In _47th International Symposium on Mathematical Foundations of Computer Science (MFCS’22)_ _(LIPIcs, Vol. 241)_. Schloss Dagstuhl – LZI, 75:1–75:16.  https://doi.org/10.4230/LIPIcs.MFCS.2022.75
  * Reingold [2008] Omer Reingold. 2008\.  Undirected Connectivity in Log-space.  _J. ACM_ 55, 4 (2008), 17:1–17:24.  https://doi.org/10.1145/1391289.1391291
  * Sherali and Adams [1990] Hanif D. Sherali and Warren P. Adams. 1990.  A Hierarchy of Relaxations Between the Continuous and Convex Hull Representations for Zero-One Programming Problems.  _SIAM J. Discret. Math._ 3, 3 (1990), 411–430.  https://doi.org/10.1137/0403036
  * Thapper and Živný [2017] Johan Thapper and Stanislav Živný. 2017\.  The Power of Sherali-Adams Relaxations for General-Valued CSPs.  _SIAM J. Comput._ 46, 4 (2017), 1241–1279.  https://doi.org/10.1137/16M1079245
  * Wrochna [2022a] Marcin Wrochna. 2022a.  A note on hardness of promise hypergraph colouring.  (2022).  https://doi.org/10.48550/arXiv.2205.14719
  * Wrochna [2022b] Marcin Wrochna. 2022b.  Notes on consistency (in minor conditions and minions). (March 2022).  unpublished manuscript.
  * Wrochna and Živný [2020] Marcin Wrochna and Stanislav Živný. 2020\.  Improved hardness for $H$-colourings of $G$-colourable graphs. In _Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’20)_. SIAM, Salt Lake City, UT, USA, 1426–1435.  https://doi.org/10.1137/1.9781611975994.86
  * Zhuk [2020] Dmitriy Zhuk. 2020\.  A Proof of the CSP Dichotomy Conjecture.  _J. ACM_ 67, 5 (2020), 30:1–30:78.  https://doi.org/10.1145/3402029