# Network Satisfaction Problems Solved by $k$-Consistency

Manuel Bodirsky<EMAIL_ADDRESS> Institut für Algebra, TU
Dresden, 01062 Dresden, Germany  Simon Knäuer<EMAIL_ADDRESS>Institut für Algebra, TU Dresden, 01062 Dresden, Germany

###### Abstract

We show that the problem of deciding for a given finite relation algebra ${\bf
A}$ whether the network satisfaction problem for ${\bf A}$ can be solved by
the $k$-consistency procedure, for some $k\in{\mathbb{N}}$, is undecidable.
For the important class of finite relation algebras ${\bf A}$ with a normal
representation, however, the decidability of this problem remains open. We
show that if ${\bf A}$ is symmetric and has a flexible atom, then the question
whether $\operatorname{NSP}({\bf A})$ can be solved by $k$-consistency, for
some $k\in{\mathbb{N}}$, is decidable (even in polynomial time in the number
of atoms of ${\bf A}$). This result follows from a more general sufficient
condition for the correctness of the $k$-consistency procedure for finite
symmetric relation algebras. In our proof we make use of a result of Alexandr
Kazda about finite binary conservative structures.

##  1 Introduction

Many computational problems in qualitative temporal and spatial reasoning can
be phrased as _network satisfaction problems (NSPs)_ for _finite relation
algebras_. Such a network consists of a finite set of nodes, and a labelling
of pairs of nodes by elements of the relation algebra. In applications, such a
network models some partial (and potentially inconsistent) knowledge that we
have about some temporal or spatial configuration. The computational task is
to replace the labels by _atoms_ of the relation algebra such that the
resulting network has an embedding into a representation of the relation
algebra. In applications, this embedding provides a witness that the input
configuration is consistent (a formal definition of relation algebras,
representations, and the network satisfaction problem can be found in Section
2.1). The computational complexity of the network satisfaction problem depends
on the fixed finite relation algebra, and is of central interest in the
mentioned application areas. Relation algebras have been studied since the
40’s with famous contributions of Tarski [Tar48], Lyndon [Lyn50], McKenzie
[McK66, McK70], and many others, with renewed interest since the 90s [HH01a,
HH01b, Hir96, HH02, Dün05, Bod18, BK21].

One of the most prominent algorithms for solving NSPs in polynomial time is
the so-called _path consistency procedure_. The path consistency procedure has
a natural generalisation to the _$k$ -consistency procedure_, for some fixed
$k\geq 3$. Such consistency algorithms have a number of advantages: e.g., they
run in polynomial time, and they are _one-sided correct_ , i.e., if they
reject an instance, then we can be sure that the instance is unsatisfiable.
Because of these properties, consistency algorithms can be used to prune the
search space in exhaustive approaches that are used if the network consistency
problem is NP-complete. The question for what temporal and spatial reasoning
problems the $k$-consistency procedure provides a necessary and sufficient
condition for satisfiability is among the most important research problems in
the area [RN07, BJ17]. The analogous problem for so-called _constraint
satisfaction problems (CSPs)_ was posed by Feder and Vardi [FV99] and has been
solved for finite-domain CSPs by Barto and Kozik [BK14]. Their result also
shows that for a given finite-domain template, the question whether the
corresponding CSP can be solved by the $k$-consistency procedure can be
decided in polynomial time.

In contrast, we show that there is no algorithm that decides for a given
finite relation algebra ${\bf A}$ whether $\operatorname{NSP}(\bf A)$ can be
solved by the $k$-consistency procedure, for some $k\in{\mathbb{N}}$. The
question is also undecidable for every fixed $k\geq 3$; in particular, there
is no algorithm that decides whether
$\operatorname{NSP}(\operatorname{\mathfrak{A}})$ can be solved by the path
consistency procedure. Our proof relies on results of Hirsch [Hir99] and
Hirsch and Hodkinson [HH01a]. The proof also shows that Hirsch’s _Really Big
Complexity Problem (RBCP;[Hir96])_ is undecidable. The RBCP asks for a
description of those finite relation algebras ${\bf A}$ whose NSP can be
solved in polynomial time.

Many of the classic examples of relation algebras that are used in temporal
and spatial reasoning, such as the point algebra, Allen’s Interval Algebra,
RCC5, RCC8, have so-called _normal representations_ , which are
representations that are particularly well-behaved from a model theory
perspective [Hir96, BJ17, Bod18]. The importance of normal representations
combined with our negative results for general finite relation algebras
prompts the question whether solvability of the NSP by the $k$-consistency
procedure can at least be characterised for relation algebras $\bf A$ with a
normal representation. Our main result is a sufficient condition that implies
that $\operatorname{NSP}({\bf A})$ can be solved by the $k$-consistency
procedure (Theorem 4.4). The condition can be checked algorithmically for a
given ${\bf A}$. Moreover, for symmetric relation algebras with a flexible
atom, which form a large subclass of the class of relation algebras with a
normal representation, our condition provides a necessary and sufficient
criterion for solvability by $k$-consistency (Theorem 5.2). We prove that the
NSP for every symmetric relation algebra with a flexible atom that cannot be
solved by the $k$-consistency procedure is already NP-complete. Finally, for
symmetric relation algebras with a flexible atom our tractability condition
can even be checked in polynomial time for a given relation algebra ${\bf A}$
(Theorem 6.2).

In our proof, we exploit a connection between the NSP for relation algebras
${\bf A}$ with a normal representation and finite-domain constraint
satisfaction problems. In a next step, this allows us to use strong results
for CSPs over finite domains. There are similarities between the fact that the
set of relations of a representation of ${\bf A}$ is closed under taking
unions on the one hand, and so-called _conservative finite-domain CSPs_
[Bul03, Bar11, Bul11, Bul16] on the other hand; in a conservative CSP the set
of allowed constraints in instances of the CSP contains all unary relations.
The complexity of conservative CSPs has been classified long before the
solution of the Feder-Vardi Dichotomy Conjecture [FV99, Bul17, Zhu17, Zhu20].
Moreover, there are particularly elegant descriptions of when a finite-domain
conservative CSP can be solved by the $k$-consistency procedure for some
$k\in\mathbb{N}$ (see, e.g., Theorem 2.17 in [Bul11]). Our approach is to turn
the similarities into a formal correspondence so that we can use these results
for finite-domain conservative CSPs to prove that $k$-consistency solves
$\operatorname{NSP}({\bf A})$. A key ingredient here is a contribution of
Kazda [Kaz15] about conservative _binary_ CSPs.

##  2 Preliminaries

A _signature_ $\tau$ is a set of function or relation symbols each of which
has an associated finite _arity_ $k\in\mathbb{N}$. A $\tau$-structure
$\operatorname{\mathfrak{A}}$ consists of a set $A$ together with a function
$f^{\operatorname{\mathfrak{A}}}\colon A^{k}\rightarrow A$ for every function
symbol $f\in\tau$ of arity $k$ and a relation
$R^{\operatorname{\mathfrak{A}}}\subseteq A^{k}$ for every relation symbol
$R\in\tau$ of arity $k$. The set $A$ is called the _domain of
$\operatorname{\mathfrak{A}}$_. Let $\operatorname{\mathfrak{A}}$ and
$\operatorname{\mathfrak{B}}$ be $\tau$-structures. The _(direct) product_
$\operatorname{\mathfrak{C}}=\operatorname{\mathfrak{A}}\times\operatorname{\mathfrak{B}}$
is the $\tau$-structure where

  * •

$A\times B$ is the domain of $\operatorname{\mathfrak{C}}$;

  * •

for every relation symbol $Q$ of arity $n\in\mathbb{N}$ and every tuple
$((a_{1},b_{1}),\ldots,(a_{n},b_{n}))\in(A\times B)^{n}$, we have that
$((a_{1},b_{1}),\ldots,(a_{n},b_{n}))\in Q^{\mathfrak{C}}$ if and only if
$(a_{1},\ldots,a_{n})\in Q^{\operatorname{\mathfrak{A}}}$ and
$(b_{1},\ldots,b_{n})\in Q^{\operatorname{\mathfrak{B}}}$;

  * •

for every function symbol $Q$ of arity $n\in\mathbb{N}$ and every tuple
$((a_{1},b_{1}),\ldots,(a_{n},b_{n}))\in(A\times B)^{n}$, we have that

$Q^{\mathfrak{C}}((a_{1},b_{1}),\ldots,(a_{n},b_{n})):=(Q^{\operatorname{\mathfrak{A}}}(a_{1},\ldots,a_{n}),Q^{\operatorname{\mathfrak{B}}}(b_{1},\ldots,b_{n})).$

We denote the (direct) product
$\operatorname{\mathfrak{A}}\times\operatorname{\mathfrak{A}}$ by
$\operatorname{\mathfrak{A}}^{2}$. The $k$-fold product
$\operatorname{\mathfrak{A}}\times\cdots\times\operatorname{\mathfrak{A}}$ is
defined analogously and denoted by $\operatorname{\mathfrak{A}}^{k}$.
Structures with a signature that only contains function symbols are called
_algebras_ and structures with purely relational signature are called
_relational structures_. Since we do not deal with signatures of mixed type in
this article, we will use the term structure for relational structures only.

###  2.1 Relation Algebras

_Relation algebras_ are particular algebras; in this section we recall their
definition and state some of their basic properties. We introduce _proper_
relation algebras, move on to abstract relation algebras, and finally define
representations of relation algebras. For an introduction to relation algebras
we recommend the textbook by Maddux [Mad06].

Proper relation algebras are algebras whose domain is a set of binary
relations over a common domain, and which are equipped with certain operations
on binary relations.

######  Definition 2.1.

Let $D$ be a set and $\mathcal{R}$ a set of binary relations over $D$ such
that
$(\mathcal{R};\cup,\bar{\phantom{o}},0,1,\operatorname{Id},\breve{\phantom{o}},\circ)$
is an algebra with operations defined as follows:

  1. 1.

$0:=\emptyset$,

  2. 2.

$1:=\bigcup\mathcal{R}$,

  3. 3.

$\operatorname{Id}:=\\{(x,x)\mid x\in D\\}$,

  4. 4.

$a\cup b:=\\{(x,y)\mid(x,y)\in a\vee(x,y)\in b\\}$,

  5. 5.

$\bar{a}:=1\setminus a$,

  6. 6.

$\breve{a}:=\\{(x,y)\mid(y,x)\in a\\}$,

  7. 7.

$a\circ b:=\\{(x,z)\mid\exists y\in D:(x,y)\in a\textup{~{} and~{} }(y,z)\in
b\\}$,

for $a,b\in\mathcal{R}$. Then
$(\mathcal{R};\cup,\bar{\phantom{o}},0,1,\operatorname{Id},\breve{\phantom{o}},\circ)$
is called a _proper relation algebra._

The class of all proper relation algebras is denoted by PA. Abstract relation
algebras are a generalisation of proper relation algebras where the domain
does not need to be a set of binary relations.

######  Definition 2.2.

An _(abstract) relation algebra_ $\bf A$ is an algebra with domain $A$ and
signature
$\\{\cup,\bar{\phantom{o}},0,1,\operatorname{Id},\breve{\phantom{o}},\circ\\}$
such that

  1. 1.

the structure $(A;\cup,\cap,\bar{\phantom{o}},0,1)$, with $\cap$ defined by
$x\cap y:=\overline{(\bar{x}\cup\bar{y})}$, is a Boolean algebra,

  2. 2.

$\circ$ is an associative binary operation on A, called _composition_ ,

  3. 3.

for all $a,b,c,\in A$: $(a\cup b)\circ c=(a\circ c)\cup(b\circ c)$,

  4. 4.

for all $a\in A$: $a\circ\operatorname{Id}=a$,

  5. 5.

for all $a\in A$: $\breve{\breve{a}}=a$,

  6. 6.

for all $a,b\in A$: $\breve{x}=\breve{a}\cup\breve{b}$ where $x:=a\cup b$,

  7. 7.

for all $a,b\in A$: $\breve{x}=\breve{b}\circ\breve{a}$ where $x:=a\circ b$,

  8. 8.

for all $a,b,c\in A$: $\bar{b}\cup(\breve{a}\circ(\overline{(a\circ
b)})=\bar{b}$.

We denote the class of all relation algebras by RA. Let
$\mathbf{A}=(A;\cup,\bar{\phantom{o}},0,1,\operatorname{Id},\breve{\phantom{o}},\circ)$
be a relation algebra. By definition, $(A;\cup,\cap,\bar{\phantom{o}},0,1)$ is
a Boolean algebra and therefore induces a partial order $\leq$ on $A$, which
is defined by $x\leq y:\Leftrightarrow x\cup y=y$. Note that for proper
relation algebras this ordering coincides with the set-inclusion order. The
minimal elements of this order in $A\setminus\\{0\\}$ are called _atoms_. The
set of atoms of $\bf A$ is denoted by $A_{0}$. Note that for the finite
Boolean algebra $(A;\cup,\cap,\bar{\phantom{o}},0,1)$ each element $a\in A$
can be uniquely represented as the union $\cup$ (or “join”) of elements from a
subset of $A_{0}$. We will often use this fact and directly denote elements of
the relation algebra $\operatorname{\mathbf{A}}$ by subsets of $A_{0}$.

By item 3. in Definition 2.2 the values of the composition operation $\circ$
in $\operatorname{\mathbf{A}}$ are completely determined by the values of
$\circ$ on $A_{0}$. This means that for a finite relation algebra the
operation $\circ$ can be represented by a multiplication table for the atoms
$A_{0}$.

An algebra with signature
$\tau=\\{\cup,\bar{\phantom{o}},0,1,\operatorname{Id},\breve{\phantom{o}},\circ\\}$
with corresponding arities $2$, $1$, $0$, $0$, $0$, $1$, and $2$ that is
isomorphic to some proper relation algebra is called _representable_. The
class of representable relation algebras is denoted by RRA. Since every proper
relation algebra and therefore also every representable relation algebra
satisfies the axioms from the previous definition we have
$\text{PA}\subseteq\text{RRA}\subseteq\text{RA}$. A classical result of Lyndon
[Lyn50] states that there exist finite relation algebras
$\operatorname{\mathbf{A}}\in\operatorname{RA}$ that are not representable; so
the inclusions above are proper. If a relation algebra
$\operatorname{\mathbf{A}}$ is representable then the isomorphism to a proper
relation algebra is usually called the _representation of $\bf A$_.

We will be interested in the model-theoretic behavior of sets of relations
which form the domain of a proper relation algebra, and therefore consider
relational structures whose relations are precisely the relations of a proper
relation algebra. If the set of relations of a relational structure
$\operatorname{\mathfrak{B}}$ forms a proper relation algebra which is a
representation of some abstract relation algebra ${\bf A}$, then it will be
convenient to also call $\operatorname{\mathfrak{B}}$ a representation of $\bf
A$.

######  Definition 2.3.

Let $\mathbf{A}\in\operatorname{RA}$. A _representation of $\mathbf{A}$_ is a
relational structure $\mathfrak{B}$ such that

  * •

$\mathfrak{B}$ is an $A$-structure, i.e., the elements of $A$ are binary
relation symbols of ${\mathfrak{B}}$;

  * •

The map $a\mapsto a^{\mathfrak{B}}$ is an isomorphism between the abstract
relation algebra $\mathbf{A}$ and the proper relation algebra
$(\mathcal{R};\cup,\bar{\phantom{o}},0,1,\operatorname{Id},\breve{\phantom{o}},\circ)$
with domain $\mathcal{R}:=\\{a^{\operatorname{\mathfrak{B}}}\mid a\in A\\}$.

Recall that the set of atoms of a relation algebra
$\mathbf{A}=(A;\cup,\bar{\phantom{o}},0,1,\operatorname{Id},\breve{\phantom{o}},\circ)$
is denoted by $A_{0}$. The following definitions are crucial for this article.

######  Definition 2.4.

A tuple $(x,y,z)\in(A_{0})^{3}$ is called an _allowed triple (of
$\operatorname{\mathbf{A}}$)_ if $z\leq x\circ y$. Otherwise, $(x,y,z)$ is
called a _forbidden triple (of $\operatorname{\mathbf{A}}$)_; in this case
$\overline{z}\cup\overline{x\circ y}=1$. We say that a relational
$A$-structure $\mathfrak{B}$ _induces a forbidden triple (from $\mathbf{A}$)_
if there exist $b_{1},b_{2},b_{3}\in B$ and $(x,y,z)\in(A_{0})^{3}$ such that
$x(b_{1},b_{2}),y(b_{2},b_{3})$ and $z(b_{1},b_{3})$ hold in
$\operatorname{\mathfrak{B}}$ and $(x,y,z)$ is a forbidden triple of
$\operatorname{\mathbf{A}}$.

Note that a representation of $\bf A$ by definition does not induce a
forbidden triple. A relation $R\subseteq A^{3}$ is called _totally symmetric_
if for every bijection $\pi\colon\\{1,2,3\\}\rightarrow\\{1,2,3\\}$ we have

$(a_{1},a_{2},a_{3})\in
R~{}\Rightarrow~{}(a_{\pi(1)},a_{\pi(2)},a_{\pi(3)})\in R.$

The following is an immediate consequence of the definition of allowed
triples.

######  Remark 2.5.

The set of allowed triples of a symmetric relation algebra
$\operatorname{\mathbf{A}}$ is totally symmetric.

###  2.2 The Network Satisfaction Problem

In this section we present computational decision problems associated with
relation algebras. We first introduce the inputs to these decision problems,
so-called $\mathbf{A}$-networks.

######  Definition 2.6.

Let $\mathbf{A}$ be a relation algebra. An _$\mathbf{A}$ -network $(V;f)$_ is
a finite set $V$ together with a partial function $f\colon E\subseteq
V^{2}\rightarrow A$, where $E$ is the domain of $f$. An $\mathbf{A}$-network
$(V;f)$ is _satisfiable in a representation_ $\mathfrak{B}$ of $\bf A$ if
there exists an assignment $s\colon V\rightarrow B$ such that for all
$(x,y)\in E$ the following holds:

$(s(x),s(y))\in f(x,y)^{\mathfrak{B}}.$

An $\mathbf{A}$-network $(V;f)$ is _satisfiable_ if there exists a
representation $\mathfrak{B}$ of $\mathbf{A}$ such that $(V;f)$ is satisfiable
in $\mathfrak{B}$.

With these notions we can define the network satisfaction problem.

######  Definition 2.7.

The _(general) network satisfaction problem_ for a finite relation algebra
$\mathbf{A}$, denoted by $\operatorname{NSP}(\bf A)$, is the problem of
deciding whether a given $\mathbf{A}$-network is satisfiable.

In the following we assume that for an $\mathbf{A}$-network $(V;f)$ it holds
that $f(V^{2})\subseteq A\setminus\\{0\\}$. Otherwise, $(V;f)$ is not
satisfiable. Note that every $\mathbf{A}$-network $(V;f)$ can be viewed as an
$A$-structure $\mathfrak{C}$ on the domain $V$: for all $x,y\in V$ in the
domain of $f$ and $a\in A$ the relation $a^{\mathfrak{C}}(x,y)$ holds if and
only if $f(x,y)=a$.

It is well-known that for relation algebras $\operatorname{\mathbf{A}}_{1}$
and $\operatorname{\mathbf{A}}_{2}$ the direct product
$\operatorname{\mathbf{A}}_{1}\times\operatorname{\mathbf{A}}_{2}$ is also a
relation algebra (see, e.g., [HH02]). We will see in Lemma 2.9 that the direct
product of representable relation algebras is also a representable relation
algebra.

######  Definition 2.8.

Let $\operatorname{\mathbf{A}}_{1}$ and $\operatorname{\mathbf{A}}_{2}$ be
representable relation algebras. Let $\operatorname{\mathfrak{B}}_{1}$ and
$\operatorname{\mathfrak{B}}_{2}$ be representations of
$\operatorname{\mathbf{A}}_{1}$ and $\operatorname{\mathbf{A}}_{2}$ with
disjoint domains. Then the _union representation_ of the direct product
$\operatorname{\mathbf{A}}_{1}\times\operatorname{\mathbf{A}}_{2}$ is the
$(A_{1}\times A_{2})$-structure
$\operatorname{\mathfrak{B}}_{1}\uplus\operatorname{\mathfrak{B}}_{2}$ on the
domain $B_{1}\uplus B_{2}$ with the following definition for all
$(a_{1},a_{2})\in A_{1}\times A_{2}$:

$(a_{1},a_{2})^{\operatorname{\mathfrak{B}}_{1}\uplus\operatorname{\mathfrak{B}}_{2}}:=a_{1}^{\operatorname{\mathfrak{B}}_{1}}\cup
a_{2}^{\operatorname{\mathfrak{B}}_{2}}.$

The following well-known lemma establishes a connection between products of
relation algebras and union representations (see, e.g., Lemma 7 in [CH04] or
Lemma 3.7 in [HH02]); it states that union representations are indeed
representations. We present the proof in Appendix A.1 to give the reader a
sense of the definition of union representations. Union representations will
be the key object in our undecidability proof for Hirsch’s Really Big
Complexity Problem.

######  Lemma 2.9.

Let $\operatorname{\mathbf{A}}_{1}$ and $\operatorname{\mathbf{A}}_{2}$ be
relation algebras. Then the following holds:

  1. 1.

If $\operatorname{\mathfrak{B}}_{1}$ and $\operatorname{\mathfrak{B}}_{2}$ are
representations of $\operatorname{\mathbf{A}}_{1}$ and
$\operatorname{\mathbf{A}}_{2}$ with disjoint domains, then
$\operatorname{\mathfrak{B}}_{1}\uplus\operatorname{\mathfrak{B}}_{2}$ is a
representation of
$\operatorname{\mathbf{A}}_{1}\times\operatorname{\mathbf{A}}_{2}$.

  2. 2.

If $\operatorname{\mathfrak{B}}$ is a representation of
$\operatorname{\mathbf{A}}_{1}\times\operatorname{\mathbf{A}}_{2}$, then there
exist representations $\operatorname{\mathfrak{B}}_{1}$ and
$\operatorname{\mathfrak{B}}_{2}$ of $\operatorname{\mathbf{A}}_{1}$ and
$\operatorname{\mathbf{A}}_{2}$ such that $\operatorname{\mathfrak{B}}$ is
isomorphic to
$\operatorname{\mathfrak{B}}_{1}\uplus\operatorname{\mathfrak{B}}_{2}$.

The following result uses Lemma 2.9 to obtain reductions between different
network satisfaction problems. A similar statement can be found in Lemma 7
from [CH04], however there the assumption on representability of the relation
algebras $\bf A$ and $\bf B$ is missing. Note that without this assumption the
statement is not longer true. Consider relation algebras $\bf A$ and $\bf B$
such that $\operatorname{NSP}(\bf A)$ is undecidable and $\bf B$ does not have
a representation. Then $\bf A\times\bf B$ does also not have a representation
(see Lemma 2.9) and hence $\operatorname{NSP}(\bf A\times\bf B)$ is trivial.
We observe that the undecidable problem $\operatorname{NSP}(\bf A)$ cannot
have a polynomial-time reduction to the trivial problem
$\operatorname{NSP}(\bf A\times\bf B)$.

######  Lemma 2.10.

Let $\bf A,\bf B\in\operatorname{RRA}$ be finite. Then there exists a
polynomial-time reduction from $\operatorname{NSP}(\bf A)$ to
$\operatorname{NSP}(\bf A\times\bf B)$.

###### Proof.

Consider the following polynomial-time reduction from $\operatorname{NSP}(\bf
A)$ to $\operatorname{NSP}(\bf A\times\bf B)$. We map a given
$\operatorname{\mathbf{A}}$-network $(V;f)$ to the $(\bf A\times\bf
B)$-network $(V;f^{\prime})$ where $f^{\prime}$ is defined by
$f^{\prime}(x,y):=(f(x,y),0)$. This reduction can be computed in polynomial
time.

Claim 1. If $(V;f)$ is satisfiable then $(V;f^{\prime})$ is also satisfiable.
Let $\operatorname{\mathfrak{A}}$ be a representation of
$\operatorname{\mathbf{A}}$ in which $(V;f)$ is satisfiable and let
$\operatorname{\mathfrak{B}}$ be an arbitrary representation of
$\operatorname{\mathbf{B}}$. By Lemma 2.9, the structure
$\operatorname{\mathfrak{A}}\uplus\operatorname{\mathfrak{B}}$ is a
representation of $\bf A\times\bf B$. Moreover, the definition of union
representations (Definition 2.8) yields that the $(\bf A\times\bf B)$-network
$(V;f^{\prime})$ is satisfiable in
$\operatorname{\mathfrak{A}}\uplus\operatorname{\mathfrak{B}}$.

Claim 2. If $(V;f^{\prime})$ is satisfiable then $(V;f)$ is satisfiable.
Assume that $(V;f^{\prime})$ is satisfiable in some representation
$\operatorname{\mathfrak{C}}$ of $\bf A\times\bf B$. By item 2 in Lemma 2.9 we
get that $\operatorname{\mathfrak{C}}$ is isomorphic to
$\operatorname{\mathfrak{A}}\uplus\operatorname{\mathfrak{B}}$, where
$\operatorname{\mathfrak{A}}$ and $\operatorname{\mathfrak{B}}$ are
representations of $\operatorname{\mathbf{A}}$ and
$\operatorname{\mathbf{B}}$. It again follows from the definition of union
representations that $(V;f)$ is satisfiable in the representation
$\operatorname{\mathfrak{A}}$ of $\operatorname{\mathbf{A}}$.

This shows the correctness of the polynomial-time reduction from
$\operatorname{NSP}(\bf A)$ to $\operatorname{NSP}(\bf A\times\bf B)$ and
finishes the proof. ∎

###  2.3 Normal Representations and Constraint Satisfaction Problems

We consider a subclass of $\operatorname{RRA}$ introduced by Hirsch in 1996.
For relation algebras $\bf A$ from this class, $\operatorname{NSP}(\bf A)$
corresponds naturally to a constraint satisfaction problem. In the following
let $\mathbf{A}$ be in $\operatorname{RRA}$. We call an $\mathbf{A}$-network
$(V;f)$ _closed_ (transitively closed in the work by Hirsch [Hir97]) if $f$ is
total and for all $x,y,z\in V$ it holds that

  * •

$f(x,x)\leq\operatorname{Id}$,

  * •

$f(x,y)=\breve{a}$ for $a={f(y,x)}$,

  * •

$f(x,z)\leq f(x,y)\circ f(y,z)$.

It is called _atomic_ if the range of $f$ only contains atoms from
$\mathbf{A}$.

######  Definition 2.11 (from [Hir96]).

Let $\mathfrak{B}$ be a representation of $\mathbf{A}$. Then $\mathfrak{B}$ is
called

  * •

_fully universal_ , if every atomic closed $\mathbf{A}$-network is satisfiable
in $\mathfrak{B}$;

  * •

_square_ , if $1^{\mathfrak{B}}=B^{2}$;

  * •

_homogeneous_ , if for every isomorphism between finite substructures of
$\mathfrak{B}$ there exists an automorphism of $\mathfrak{B}$ that extends
this isomorphism;

  * •

_normal_ , if it is fully universal, square and homogeneous.

We now investigate the connection between
$\operatorname{NSP}(\operatorname{\mathbf{A}})$ for a finite relation algebra
with a normal representation $\operatorname{\mathfrak{B}}$ and constraint
satisfaction problems. Let $\tau$ be a finite relational signature and let
$\operatorname{\mathfrak{B}}$ be a (finite or infinite) $\tau$-structure. Then
the _constraint satisfaction problem for $\operatorname{\mathfrak{B}}$_,
denoted by $\operatorname{CSP}(\operatorname{\mathfrak{B}})$, is the
computational problem of deciding whether a finite input structure
$\operatorname{\mathfrak{A}}$ has a homomorphism to
$\operatorname{\mathfrak{B}}$. The structure $\operatorname{\mathfrak{B}}$ is
called the template of $\operatorname{CSP}(\operatorname{\mathfrak{B}})$.

Consider the following translation which associates to each
$\mathbf{A}$-network $(V;f)$ an $A$-structure $\operatorname{\mathfrak{C}}$ as
follows: the set $V$ is the domain of $\operatorname{\mathfrak{C}}$ and
$(x,y)\in C^{2}$ is in a relation $a^{\operatorname{\mathfrak{C}}}$ if and
only if $(x,y)$ is in the domain of $f$ and $f(x,y)=a$ holds. For the other
direction let $\operatorname{\mathfrak{C}}$ be an $A$-structure with domain
$C$ and consider the $\mathbf{A}$-network $(C;f)$ with the following
definition: for every $x,y\in C$, if $(x,y)$ does not appear in any relation
of $\operatorname{\mathfrak{C}}$ we leave $f(x,y)$ undefined, otherwise let
$a_{1}(x,y),\ldots,a_{n}(x,y)$ be all atomic formulas that hold in
$\operatorname{\mathfrak{C}}$. We compute in $\mathbf{A}$ the element
$a:=a_{1}\cap\dots\cap a_{n}$ and define $f(x,y):=a$.

The following theorem is based on the natural 1-to-1 correspondence between
$\mathbf{A}$-networks and $A$-structures; it subsumes the connection between
network satisfaction problems and constraint satisfaction problems.

######  Proposition 2.12 (Proposition 1.3.16 in [Bod12], see also [BJ17,
Bod18]).

Let $\mathbf{A}\in\operatorname{RRA}$ be finite. Then the following holds:

  1. 1.

$\mathbf{A}$ has a representation $\operatorname{\mathfrak{B}}$ such that
$\operatorname{NSP}(\mathbf{A})$ and $\operatorname{CSP}(\mathfrak{B})$ are
the same problem up to the translation between $\mathbf{A}$-networks and
$A$-structures.

  2. 2.

If $\mathbf{A}$ has a normal representation $\operatorname{\mathfrak{B}}$ the
problems $\operatorname{NSP}(\mathbf{A})$ and
$\operatorname{CSP}(\mathfrak{B})$ are the same up to the translation between
$\mathbf{A}$-networks and $A$-structures.

Usually, normal representations of relation algebras are infinite relational
structures. This means that the transfer from NSPs to CSPs from Proposition
2.12 results in CSPs over infinite templates, as in the following example.

######  Example 2.13.

Consider the _point algebra_ $\mathbf{P}$. The set of atoms of $\mathbf{P}$ is
$P_{0}=\\{\operatorname{Id},<,>\\}$. The composition operation $\circ$ on the
atoms is given by the multiplication table in Figure 1. The table completely
determines the composition operation $\circ$ on all elements of $\mathbf{P}$.

$~{}\circ~{}$ | $~{}\operatorname{Id}~{}$ | $~{}<~{}$ | $~{}>~{}$
---|---|---|---
$\operatorname{Id}$ | $\operatorname{Id}$ | $<$ | $>$
$<$ | $<$ | $<$ | $1$
$>$ | $>$ | $1$ | $>$
Figure 1: Multiplication table of the point algebra $\mathbf{P}$.

Note that the structure
$\mathfrak{P}:=(\mathbb{Q};~{}\emptyset,<,>,=,\leq,\geq,\not=,\mathbb{Q}^{2})$
is the normal representation of $\mathbf{P}$ and therefore
$\operatorname{NSP}(\mathbf{P})$ and $\operatorname{CSP}(\mathfrak{P})$ are
the same problems up to the translation between networks and structures.

###  2.4 The Universal-Algebraic Approach

We introduce in this section the study of CSPs via the universal-algebraic
approach.

####  2.4.1 Polymorphisms

Let $\tau$ be a finite relational signature. A _polymorphism_ of a
$\tau$-structure $\operatorname{\mathfrak{B}}$ is a homomorphism $f$ from
$\operatorname{\mathfrak{B}}^{k}$ to $\operatorname{\mathfrak{B}}$, for some
$k\in\mathbb{N}$ called the _arity of $f$_. We write
$\operatorname{Pol}(\operatorname{\mathfrak{B}})$ for the set of all
polymorphisms of $\operatorname{\mathfrak{B}}$. The set of polymorphisms is
closed under composition, i.e., for all $n$-ary
$f\in\operatorname{Pol}(\operatorname{\mathfrak{B}})$ and $s$-ary
$g_{1},\ldots,g_{n}\in\operatorname{Pol}(\operatorname{\mathfrak{B}})$ it
holds that
$f(g_{1},\ldots,g_{n})\in\operatorname{Pol}(\operatorname{\mathfrak{B}})$,
where $f(g_{1},\ldots,g_{n})$ is a homomorphism from
$\operatorname{\mathfrak{B}}^{s}$ to $\operatorname{\mathfrak{B}}$ defined as
follows

$f(g_{1},\ldots,g_{n})(x_{1},\ldots,x_{s}):=f(g_{1}(x_{1},\ldots,x_{s}),\ldots,g_{n}(x_{1},\ldots,x_{s})).$

If $r_{1},\dots,r_{n}\in B^{k}$ and $f\colon B^{n}\to B$ an $n$-ary operation,
then we write $f(r_{1},\ldots,r_{n})$ for the $k$-tuple obtained by applying
$f$ component-wise to the tuples $r_{1},\ldots,r_{n}$. We say that $f\colon
B^{n}\to B$ _preserves_ a $k$-ary relation $R\subseteq B^{k}$ if for all
$r_{1},\ldots,r_{n}\in R$ it holds that $f(r_{1},\ldots,r_{n})\in R$. We want
to remark that the polymorphisms of $\operatorname{\mathfrak{B}}$ are
precisely those operations that preserve all relations from
$\operatorname{\mathfrak{B}}$.

A first-order $\tau$-formula $\varphi(x_{1},\ldots,x_{n})$ is called
_primitive positive (pp)_ if it has the form

$\exists x_{n+1},\ldots,x_{m}(\varphi_{1}\wedge\cdots\wedge\varphi_{s})$

where $\varphi_{1},\ldots,\varphi_{s}$ are atomic $\tau$-formulas, i.e.,
formulas of the form $R(y_{1},\ldots,y_{l})$ for $R\in\tau$ and
$y_{i}\in\\{x_{1},\ldots,x_{m}\\}$, of the form $y=y^{\prime}$ for
$y,y^{\prime}\in\\{x_{1},\ldots,x_{m}\\}$, or of the form $\bot$. We say that
a relation $R$ is _primitively positively definable over
$\operatorname{\mathfrak{A}}$_ if there exists a primitive positive
$\tau$-formula $\varphi(x_{1},\ldots,x_{n})$ such that $R$ is definable over
$\operatorname{\mathfrak{A}}$ by $\varphi(x_{1},\ldots,x_{n})$. The following
result puts together polymorphisms and primitive positive logic.

######  Proposition 2.14 ([Gei68], [BKKR69]).

Let $\operatorname{\mathfrak{B}}$ be a $\tau$-structure with a finite domain.
Then the set of primitive positive definable relations in
$\operatorname{\mathfrak{B}}$ is exactly the set of relations preserved by
$\operatorname{Pol}(\operatorname{\mathfrak{B}})$.

####  2.4.2 Atom Structures

In this section we introduce for every finite $\mathbf{A}\in\operatorname{RA}$
an associated finite structure, called the _atom structure_ of $\bf A$. If
$\operatorname{\mathbf{A}}$ has a fully universal representation, then there
exists a polynomial-time reduction from
$\operatorname{NSP}(\operatorname{\mathbf{A}})$ to the finite-domain
constraint satisfaction problem
$\operatorname{CSP}(\operatorname{\mathfrak{A}}_{0})$ (Proposition 2.16).
Hence, this reduction provides polynomial-time algorithms to solve NSPs,
whenever the CSP of the associated atom structure can be solved in polynomial-
time. For a discussion of the atom structure and related objects we recommend
Section 4 in [BK22].

######  Definition 2.15.

The _atom structure of $\bf A\in\operatorname{RA}$_ is the finite relational
structure ${\operatorname{\mathfrak{A}_{0}}}$ with domain $A_{0}$ and the
following relations:

  * •

for every $x\in A$ the unary relation
$x^{\operatorname{\mathfrak{A}_{0}}}:=\\{a\in A_{0}\mid a\leq x\\}$,

  * •

the binary relation $E^{\operatorname{\mathfrak{A}_{0}}}:=\\{(a_{1},a_{2})\in
A_{0}^{2}\mid\breve{a_{1}}=a_{2}\\}$,

  * •

the ternary relation
$R^{\operatorname{\mathfrak{A}_{0}}}:=\\{(a_{1},a_{2},a_{3})\in A_{0}^{3}\mid
a_{3}\leq a_{1}\circ a_{2}\\}$.

Note that $\operatorname{\mathfrak{A}_{0}}$ has all subsets of $A_{0}$ as
unary relations and that the relation $R^{\operatorname{\mathfrak{A}_{0}}}$
consists of the allowed triples of $\bf A\in\operatorname{RRA}$. We say that
an operation _preserves the allowed triples_ if it preserves the relation
$R^{\operatorname{\mathfrak{A}_{0}}}$.

######  Proposition 2.16 ([BK21, BK22]).

Let $\mathfrak{B}$ be a fully universal representation of a finite
$\mathbf{A}\in\operatorname{RRA}$. Then there is a polynomial-time reduction
from $\operatorname{CSP}(\mathfrak{B})$ to
$\operatorname{CSP}({\operatorname{\mathfrak{A}_{0}}})$.

####  2.4.3 Conservative Clones

Let $\operatorname{\mathfrak{B}}$ be a finite $\tau$-structure. An operation
$f\colon B^{n}\to B$ is called _conservative_ if for all
$x_{1},\ldots,x_{n}\in B$ it holds that
$f(x_{1},\ldots,x_{n})\in\\{x_{1},\ldots,x_{n}\\}$. The operation clone
$\operatorname{Pol}(\operatorname{\mathfrak{B}})$ is _conservative_ if every
$f\in\operatorname{Pol}(\operatorname{\mathfrak{B}})$ is conservative. We call
a relational structure $\operatorname{\mathfrak{B}}$ _conservative_ if
$\operatorname{Pol}(\operatorname{\mathfrak{B}})$ is conservative.

######  Remark 2.17.

Let $\operatorname{\mathfrak{A}_{0}}$ be the atom structure of a finite
relation algebra $\operatorname{\mathbf{A}}$. Every
$f\in\operatorname{Pol}(\operatorname{\mathfrak{A}_{0}})$ preserves all
subsets of $A_{0}$, and is therefore conservative. Hence,
$\operatorname{Pol}(\operatorname{\mathfrak{A}_{0}})$ is conservative.

This remark justifies our interest in the computational complexity of certain
CSPs where the template has conservative polymorphisms. Their complexity can
be studied via universal algebraic methods as we will see in the following. We
start with some definitions. An operation $f\colon B^{3}\to B$ is called

  * •

a _majority operation_ if $\forall x,y\in B.f(x,x,y)=f(x,y,x)=f(y,x,x)=x$;

  * •

a _minority operation_ if $\forall x,y\in B.f(x,x,y)=f(x,y,x)=f(y,x,x)=y$.

An operation $f\colon B^{n}\to B$, for $n\geq 2$, is called

  * •

a _cyclic operation_ if $\forall x_{1},\ldots,x_{n}\in
B.f(x_{1},\ldots,x_{n})=f(x_{n},x_{1},\ldots,x_{n-1})$;

  * •

a _weak near-unanimity operation_ if

$\forall x,y\in B.f(x,\ldots,x,y)=f(x,\ldots,x,y,x)=\ldots=f(y,x,\ldots,x);$

  * •

a _Siggers operation_ if $n=6$ and $\forall x,y\in
B.f(x,x,y,y,z,z)=f(y,z,x,z,x,y).$

The following terminology was introduced by Bulatov and has proven to be
extremely powerful, especially in the context of conservative clones.

######  Definition 2.18 ([Bul03, Bul11]).

A pair $(a,b)\in B^{2}$ is called a _semilattice edge_ if there exists
$f\in\operatorname{Pol}(\operatorname{\mathfrak{B}})$ of arity two such that
$f(a,b)=b=f(b,a)=f(b,b)$ and $f(a,a)=a$. We say that a two-element set
$\\{a,b\\}\subseteq B$ _has a semilattice edge_ if $(a,b)$ or $(b,a)$ is a
semilattice edge.

A two-element subset $\\{a,b\\}$ of $B$ is called a _majority edge_ if neither
$(a,b)$ nor $(b,a)$ is a semilattice edge and there exists an
$f\in\operatorname{Pol}(\operatorname{\mathfrak{B}})$ of arity three whose
restriction to $\\{a,b\\}$ is a majority operation.

A two-element subset $\\{a,b\\}$ of $B$ is called an _affine edge_ if it is
not a majority edge, if neither $(a,b)$ nor $(b,a)$ is a semilattice edge, and
there exists an $f\in\operatorname{Pol}(\operatorname{\mathfrak{B}})$ of arity
three whose restriction to $\\{a,b\\}$ is a minority operation.

If $S\subseteq B$ and $(a,b)\in S^{2}$ is a semilattice edge then we say that
_$(a,b)$ is a semilattice edge on $S$_. Similarly, if $\\{a,b\\}\subseteq S$
is a majority edge (affine edge) then we say that $\\{a,b\\}$ is a _majority
edge on $S$_ (_affine edge on $S$_).

The main result about conservative finite structures and their CSPs is the
following dichotomy, first proved by Bulatov, 14 years before the proof of the
Feder-Vardi conjecture.

######  Theorem 2.19 ([Bul03]; see also [Bar11, Bul11, Bul16]).

Let $\operatorname{\mathfrak{B}}$ be a finite structure with a finite
relational signature such that
$\operatorname{Pol}(\operatorname{\mathfrak{B}})$ is conservative. Then
precisely one of the following holds:

  1. 1.

$\operatorname{Pol}(\operatorname{\mathfrak{B}})$ contains a Siggers
operation; in this case, $\operatorname{CSP}(\operatorname{\mathfrak{B}})$ is
in P.

  2. 2.

There exist distinct $a,b\in B$ such that for every
$f\in\operatorname{Pol}(\operatorname{\mathfrak{B}})^{(n)}$ the restriction of
$f$ to $\\{a,b\\}^{n}$ is a projection. In this case,
$\operatorname{CSP}(\operatorname{\mathfrak{B}})$ is NP-complete.

Note that this means that $\operatorname{Pol}(\operatorname{\mathfrak{B}})$
contains a Siggers operation if and only if for all two elements $a,b\in B$
the set $\\{a,b\\}$ is a majority edge, an affine edge, or there is a
semilattice edge on $\\{a,b\\}$.

###  2.5 The $k$-Consistency Procedure

We present in the following the $k$-consistency procedure. It was introduced
in [ABD07] for finite structures and extended to infinite structures in
several equivalent ways, for example in terms of Datalog programs, existential
pebble games, and finite variable logics [BD13]. Also see [MNPW21] for recent
results about the power of $k$-consistency for infinite-domain CSPs.

Let $\tau$ be a finite relational signature and let $k,l\in\mathbb{N}$ with
$k<l$ and let $\operatorname{\mathfrak{B}}$ be a fixed $\tau$-structures with
finitely many orbits of $l$-tuples. We define
$\operatorname{\mathfrak{B}}^{\prime}$ to be the expansion of
$\operatorname{\mathfrak{B}}$ by all orbits of $n$-tuples for every $n\leq l$.
We denote the extended signature of $\operatorname{\mathfrak{B}}^{\prime}$ by
$\tau^{\prime}$. Let $\operatorname{\mathfrak{A}}$ be an arbitrary finite
$\tau$-structure. A _partial $l$-decoration of $\operatorname{\mathfrak{A}}$_
is a set $g$ of atomic $\tau^{\prime}$-formulas such that

  1. 1.

the variables of the formulas from $g$ are a subset of $A$ and denoted by
$\operatorname{Var}(g)$,

  2. 2.

$|\operatorname{Var}(g)|\leq l$,

  3. 3.

the $\tau$-formulas in $g$ hold in $\operatorname{\mathfrak{A}}$, where
variables are interpreted as domain elements of $\operatorname{\mathfrak{A}}$,

  4. 4.

the conjunction over all formulas in $g$ is satisfiable in
$\operatorname{\mathfrak{B}}^{\prime}$.

A partial $l$-decoration $g$ of $\operatorname{\mathfrak{A}}$ is called
_maximal_ if there exists no partial $l$-decoration $h$ of
$\operatorname{\mathfrak{A}}$ with
$\operatorname{Var}(g)=\operatorname{Var}(h)$ such that $g\subsetneq h$. We
denote the set of maximal partial $l$-decorations of
$\operatorname{\mathfrak{A}}$ by
$\mathcal{R}^{l}_{\operatorname{\mathfrak{A}}}$. Note that a fixed finite set
of at most $l$ variables, there are only finitely many partial $l$-decorations
of $\operatorname{\mathfrak{A}}$, because $\operatorname{\mathfrak{B}}$ has by
assumption finitely many orbits of $l$-tuples. Since this set is constant and
can be precomputed, the set $\mathcal{R}^{l}_{\operatorname{\mathfrak{A}}}$
can be computed efficiently. Then the _$(k,l)$ -consistency procedure for
$\operatorname{\mathfrak{B}}$_ is the following algorithm.

1

2

Input : A finite $\tau$-structure $\operatorname{\mathfrak{A}}$.

3

4compute $\mathcal{H}:=\mathcal{R}^{l}_{\operatorname{\mathfrak{A}}}$.

5

6repeat

7 For every $f\in\mathcal{H}$ with $\operatorname{Var}(f)\leq k$ and every
$U\subseteq A$ with $|U|\leq l-k$, if there does not exist $g\in\mathcal{H}$
with $f\subseteq g$ and $U\subseteq\operatorname{Dom}(g)$, then remove $f$
from $\mathcal{H}$.

8 until  _$\mathcal{H}$ does not change_

9 if  _$\mathcal{H}$ is empty_ then

10 return Reject.

11 else

12 return Accept.

13

Algorithm 1 $(k,l)$-consistency procedure for $\operatorname{\mathfrak{B}}$

Since $\mathcal{R}^{l}_{\operatorname{\mathfrak{A}}}$ is of polynomial size
(in the size of $A$) and the $(k,l)$-consistency procedure removes in step 3.
at least one element from $\mathcal{R}^{l}_{\operatorname{\mathfrak{A}}}$ the
algorithm has a polynomial run time. The $(k,k+1)$-consistency procedure is
also called _$k$ -consistency procedure_. The $(2,3)$-consistency procedure is
called _path consistency procedure_.111Some authors also call it the _strong
path consistency algorithm_ , because some forms of the definition of the path
consistency procedure are only equivalent to our definition of the path
consistency procedure if $\operatorname{\mathfrak{B}}$ has a transitive
automorphism group.

######  Definition 2.20.

Let $\operatorname{\mathfrak{B}}$ be a relation $\tau$-structure as defined
before. Then the _$(k,l)$ -consistency procedure for
$\operatorname{\mathfrak{B}}$ solves
$\operatorname{CSP}(\operatorname{\mathfrak{B}})$_ if the satisfiable
instances of $\operatorname{CSP}(\operatorname{\mathfrak{B}})$ are precisely
the accepted instances of the $(k,l)$-consistency procedure.

######  Remark 2.21.

Let $\operatorname{\mathbf{A}}$ be a relation algebra with a normal
representation $\operatorname{\mathfrak{B}}$. We will in the following say
that the $k$-consistency procedure solves
$\operatorname{NSP}(\operatorname{\mathbf{A}})$ if it solves
$\operatorname{CSP}(\operatorname{\mathfrak{B}})$. This definition is
justified by the correspondence of NSPs and CSPs from Theorem 2.12.

######  Theorem 2.22 ([KKVW15]).

Let $\operatorname{\mathfrak{B}}$ be a finite $\tau$-structure. Then the
following statements are equivalent:

  1. 1.

There exist $k\in\mathbb{N}$ such that the $k$-consistency procedure solves
$\operatorname{CSP}(\operatorname{\mathfrak{B}})$.

  2. 2.

$\operatorname{\mathfrak{B}}$ has a $3$-ary weak near-unanimity polymorphism
$f$ and a $4$-ary weak near-unanimity polymorphism $g$ such that: $\forall
x,y,z\in B.~{}f(y,x,x)=g(y,x,x,x).$

Let $\operatorname{\mathfrak{A}_{0}}$ be the atom structure of a relation
algebra $\operatorname{\mathbf{A}}$ with a normal representation
$\operatorname{\mathfrak{B}}$. We finish this section by connecting the
solvability of $\operatorname{CSP}(\operatorname{\mathfrak{A}_{0}})$ by
$k$-consistency (or its characterization in terms of polymorphims from the
previous proposition) with the solvability of
$\operatorname{CSP}(\operatorname{\mathfrak{B}})$ by $k$-consistency. By
Remark 2.21 this gives a criterion for the solvability of
$\operatorname{NSP}(\operatorname{\mathbf{A}})$ by the $k$-consistency
procedure.

The following theorem is from [MNPW21] building on ideas from [BM18]. We
present it here in a specific formulation that already incorporates a
correspondence between polymorphisms of the atom structure and canonical
operations. For more details see [BK21, BK22].

######  Theorem 2.23 ([MNPW21]).

Let $\operatorname{\mathfrak{B}}$ be a normal representation of a finite
relation algebra $\operatorname{\mathbf{A}}$ and
$\operatorname{\mathfrak{A}_{0}}$ the atom structure
$\operatorname{\mathbf{A}}$. If
$\operatorname{Pol}(\operatorname{\mathfrak{A}_{0}})$ contains a $3$-ary weak
near-unanimity polymorphism $f$ and a $4$-ary weak near-unanimity polymorphism
$g$ such that

$\forall x,y,z\in B.~{}f(y,x,x)=g(y,x,x,x),$

then $\operatorname{NSP}(\operatorname{\mathbf{A}})$ is solved by the
$(4,6)$-consistency algorithm.

##  3 The Undecidability of RBCP, CON, and PC

In order to view RBCP as a decision problem, we need the following
definitions. Let $\operatorname{FRA}$ be the set of all relation algebras $\bf
A$ with domain $\mathcal{P}(\\{1,\ldots,n\\})$.

######  Definition 3.1 (RBCP).

We define the following subsets of $\operatorname{FRA}$:

  * •

$\operatorname{RBCP}$ denotes the set such that $\operatorname{NSP}({\bf A})$
is in P.

  * •

$\operatorname{RBCP}^{c}$ denotes
$\operatorname{FRA}\setminus\operatorname{RBCP}$.

  * •

$\operatorname{CON}$ denotes the set such that $\operatorname{NSP}({\bf A})$
is solved by $k$-consistency for some $k\in\mathbb{N}$.

  * •

$\operatorname{PC}$ denotes the set such that $\operatorname{NSP}({\bf A})$ is
solved by path consistency.

The following theorem is our first result. Note that this can be seen as a
negative answer to Hirsch’s Really Big Complexity Problem [Hir96].

######  Theorem 3.2.

$\operatorname{RBCP}$ is undecidable, $\operatorname{CON}$ is undecidable, and
$\operatorname{PC}$ is undecidable.

In our undecidability proofs we reduce from the following well-known
undecidable problem for relation algebras [HH01a].

######  Definition 3.3 (Rep).

Let $\operatorname{Rep}$ be the computational problem of deciding for a given
$\bf A\in\operatorname{FRA}$ whether $\bf A$ has a representation.

In our proof we also use the fact that there exists ${\bf
U}\in\operatorname{FRA}$ such that $\operatorname{NSP}({\bf U})$ is
undecidable [Hir99]. Note that ${\bf U}\in\operatorname{Rep}$ since the
network satisfaction problem for non-representable relation algebras is
trivial and therefore decidable.

###### Proof of Theorem 3.2.

We reduce the problem $\operatorname{Rep}$ to $\operatorname{RBCP}^{c}$.
Consider the following reduction
$f\colon\operatorname{FRA}\to\operatorname{FRA}$. For a given $\bf
A\in\operatorname{FRA}$, we define $f({\bf A}):={\bf A}\times{\bf U}$.

Claim 1. If ${\bf A}\in\operatorname{Rep}$ then $f({\bf
A})\in\operatorname{RBCP}^{c}$. If ${\bf A}$ is representable, then ${\bf
A}\times{\bf U}$ is representable by the first part of Lemma 2.9. Then there
is a polynomial-time reduction from $\operatorname{NSP}({\bf U})$ to
$\operatorname{NSP}({\bf A}\times{\bf U})$ by Lemma 2.10. This shows that
$\operatorname{NSP}({\bf A}\times{\bf U})$ is undecidable, and hence $f({\bf
A})$ is in $\operatorname{RBCP}^{c}$.

Claim 2. If ${\bf A}\in\operatorname{FRA}\setminus\operatorname{Rep}$ then
$f({\bf A})\in\operatorname{RBCP}$. If A is not representable, then ${\bf
A}\times{\bf U}$ is not representable by the second part of Lemma 2.9, and
hence $\operatorname{NSP}({\bf A}\times{\bf U})$ is trivial and in P, and
therefore in $\operatorname{RBCP}$.

Clearly, $f$ is computable (even in polynomial time). Since
$\operatorname{Rep}$ is undecidable [HH01a], this shows that
$\operatorname{RBCP}^{c}$, and hence $\operatorname{RBCP}$, is undecidable as
well. The proof for $\operatorname{CON}$ and $\operatorname{PC}$ is analogous;
all we need is the fact that $\operatorname{NSP}({\bf
U})\notin\operatorname{CON}$ and $\operatorname{NSP}({\bf
U})\notin\operatorname{PC}$. ∎

##  4 Tractability via $k$-Consistency

We provide in this section a criterion that ensures solvability of NSPs by the
$k$-consistency procedure (Theorem 4.4). A relation algebra $\mathbf{A}$ is
called _symmetric_ if all its elements are symmetric, i.e., $\breve{a}=a$ for
every $a\in A$. We will see in the following that the assumption on
$\mathbf{A}$ to be symmetric will simplify the atom structure $A_{0}$ of
$\operatorname{\mathbf{A}}$, which has some advantages in the upcoming
arguments.

######  Definition 4.1.

Let $\bf A$ be a finite symmetric relation algebra with set of atoms $A_{0}$.
We say that $\bf A$ admits a _Siggers behavior_ if there exists an operation
$s\colon A_{0}^{6}\rightarrow A_{0}$ such that

  1. 1.

$s$ preserves the allowed triples of $\mathbf{A}$,

  2. 2.

$\forall x_{1},\ldots,x_{6}\in
A_{0}.~{}s(x_{1},\ldots,x_{6})\in\\{x_{1},\ldots,x_{6}\\}$,

  3. 3.

$s$ satisfies the Siggers identity: $\forall x,y,z\in
A_{0}.~{}s(x,x,y,y,z,z)=s(y,z,x,z,x,y).$

######  Remark 4.2.

We mention that if $\bf A$ has a normal representation
$\operatorname{\mathfrak{B}}$, then $\bf A$ admits a Siggers behavior if and
only if $\operatorname{\mathfrak{B}}$ has a pseudo-Siggers polymorphism which
is canonical with respect to
$\operatorname{Aut}(\operatorname{\mathfrak{B}})$; see [BM18].

We say that a finite symmetric relation algebra $\bf A$ _has all $1$-cycles_
if for every $a\in A_{0}$ the triple $(a,a,a)$ is allowed. Details on the
notion of cycles from the relation algebra perspective can be found in
[Mad06]. The relevance of the existence of 1-cycles for constraint
satisfaction comes from the following observation.

######  Lemma 4.3.

Let $\operatorname{\mathbf{A}}$ be a finite symmetric relation algebra with a
normal representation $\operatorname{\mathfrak{B}}$ that has a binary
injective polymorphism. Then $\operatorname{\mathbf{A}}$ has all $1$-cycles.

###### Proof.

Let $i$ be a binary injective polymorphism of $\operatorname{\mathfrak{B}}$
and let $a\in A_{0}$ be arbitrary. Consider $x_{1},x_{2},y_{1},y_{2}\in B$
such that $a^{\operatorname{\mathfrak{B}}}(x_{1},x_{2})$ and
$a^{\operatorname{\mathfrak{B}}}(y_{1},y_{2})$. The application of $i$ on the
tuples $(x_{1},x_{1},x_{2})$ and $(y_{1},y_{2},y_{2})$ results in a
substructure of $\operatorname{\mathfrak{B}}$ that witnesses that $(a,a,a)$ is
an allowed triple. ∎

######  Theorem 4.4.

Let $\bf A$ be a finite symmetric relation algebra with a normal
representation $\operatorname{\mathfrak{B}}$. Suppose that the following
holds:

  1. 1.

$\bf A$ has all $1$-cycles.

  2. 2.

$\bf A$ admits a Siggers behavior.

Then the $\operatorname{NSP}(\mathbf{A})$ can be solved by the
$(4,6)$-consistency procedure.

We will outline the proof of Theorem 4.4 and cite some results from the
literature that we will use. Assume that $\operatorname{\mathbf{A}}$ is a
finite symmetric relation algebra that satisfies the assumptions of Theorem
4.4. Since $\operatorname{\mathbf{A}}$ admits a Siggers behavior there exists
an operation $s\colon A_{0}^{6}\rightarrow A_{0}$ that is by 1. and 2. in
Definition 4.1 a polymorphism of the atom structure
$\operatorname{\mathfrak{A}_{0}}$ (see Paragraph 2.4.2). By Remark 2.17,
$\operatorname{Pol}(\operatorname{\mathfrak{A}_{0}})$ is a conservative
operation clone. Recall the notion of semilattice, majority, and affine edges
for conservative clones (cf. Definition 2.18). Since $s$ is by 3. in
Definition 4.1 a Siggers operation, Theorem 2.19 implies that every edge in
$\operatorname{\mathfrak{A}_{0}}$ is semilattice, majority, or affine.

Our goal is to show that there are no affine edges in
$\operatorname{\mathfrak{A}_{0}}$, since this implies that there exists
$k\in\mathbb{N}$ such that
$\operatorname{CSP}(\operatorname{\mathfrak{A}_{0}})$ can be solved by
$k$-consistency [Bul11]. We present this fact here via the characterization of
$(k,l)$-consistency in terms of weak near-unanimity polymorphisms from Theorem
2.22.

######  Proposition 4.5 (cf. Corollary 3.2 in [Kaz15]).

Let $\operatorname{\mathfrak{A}_{0}}$ be a finite conservative relational
structure with a Siggers polymorphism and no affine edge. Then
$\operatorname{\mathfrak{A}_{0}}$ has a $3$-ary weak near-unanimity
polymorphism $f$ and a $4$-ary weak near-unanimity polymorphism $g$ such that

$\forall x,y,z\in B.~{}f(y,x,x)=g(y,x,x,x).$

Note that the existence of the weak near-unanimity polymorphisms from
Proposition 4.5 would finish the proof of Theorem 4.4, because Theorem 2.23
implies that in this case $\operatorname{NSP}(\mathbf{A})$ can be solved by
the $(4,6)$-consistency procedure. We therefore want to prove that there are
no affine edges in $\operatorname{\mathfrak{A}_{0}}$. We start in Section B.1
by analyzing the different types of edges in the atom structure
$\operatorname{\mathfrak{A}_{0}}$ and obtain results about their appearance.

Fortunately, there is the following result by Alexandr Kazda about binary
structures with a conservative polymophism clone. A _binary structure_ is a
structure where all relations have arity at most two.

######  Theorem 4.6 (Theorem 4.5 in [Kaz15]).

If $\operatorname{\mathfrak{A}}$ is a finite binary conservative relational
structure with a Siggers polymorphism, then $\operatorname{\mathfrak{A}}$ has
no affine edges.

Notice that we cannot simply apply this theorem to the atom structure
$\operatorname{\mathfrak{A}_{0}}$, since the maximal arity of its relations is
three. We circumvent this obstacle by defining for
$\operatorname{\mathfrak{A}_{0}}$ a closely related binary structure
$\operatorname{\mathfrak{A}^{b}_{0}}$, which we call the “binarisation of
$\operatorname{\mathfrak{A}_{0}}$”. In Section B.2 we give the formal
definition of $\operatorname{\mathfrak{A}^{b}_{0}}$ and investigate how
$\operatorname{Pol}(\operatorname{\mathfrak{A}_{0}})$ and
$\operatorname{Pol}(\operatorname{\mathfrak{A}^{b}_{0}})$ relate to each
other. It follows from these observations that
$\operatorname{\mathfrak{A}^{b}_{0}}$ does not have an affine edge. In other
words, it only has semilattice and majority edges. The crucial step in our
proof is to transfer a witness of this fact to
$\operatorname{\mathfrak{A}_{0}}$ and conclude that also
$\operatorname{\mathfrak{A}_{0}}$ has no affine edge. This is done in Section
B.3.

##  5 $k$-Consistency and Symmetric Flexible-Atom Algebras

We apply our result from Section 4 to the class of finite symmetric relation
algebras with a flexible atom and obtain a $k$-consistency versus NP-complete
complexity dichotomy.

A finite relation algebra $\operatorname{\mathbf{A}}$ is called _integral_ if
the element $\operatorname{Id}$ is an atom of $\operatorname{\mathbf{A}}$,
i.e., $\operatorname{Id}\in A_{0}$. We define flexible atoms for integral
relation algebras only. For a discussion about integrality and flexible atoms
consider Section 3 in [BK22].

######  Definition 5.1.

Let $\mathbf{A}\in\operatorname{RA}$ be finite and integral. An atom $s\in
A_{0}$ is called _flexible_ if for all $a,b\in
A\setminus\\{\operatorname{Id}\\}$ it holds that $s\leq a\circ b$.

Relation algebras with a flexible atom have been studied intensively in the
context of the _flexible atoms conjecture_ [Mad94, AMM08]. It can be shown
easily that finite relation algebras with a flexible atom have a normal
representation [BK21, BK22]. In [BK22] the authors obtained a P versus NP-
complete complexity dichotomy for NSPs of finite symmetric relation algebras
with a flexible atom (assuming P $\neq$ NP). In the following we strengthen
this result and prove that every problem in this class can be solved by
$k$-consistency for some $k\in\mathbb{N}$ or is NP-complete (without any
complexity-theoretic assumptions).

We combine Theorem 4.4 with the main result of [BK22] to obtain the following
characterization for NSPs of finite symmetric relation algebras with a
flexible atom that are solved by the $(4,6)$-consistency procedure. Note that
the difference of Theorem 5.2 and the related result in [BK22] is the
algorithm that solves the problems in P.

######  Theorem 5.2.

Let $\operatorname{\mathbf{A}}$ be a finite symmetric integral relation
algebra with a flexible atom. Then the following are equivalent:

  * •

$\operatorname{\mathbf{A}}$ admits a Siggers behavior.

  * •

$\operatorname{NSP}(\mathbf{A})$ can be solved by the $(4,6)$-consistency
procedure.

###### Proof.

Every finite symmetric relation algebra $\operatorname{\mathbf{A}}$ with a
flexible atom has a normal representation $\operatorname{\mathfrak{B}}$ by
Proposition 3.5 in [BK22].

If the first item holds it follows from Proposition 6.1. in [BK22] that
$\operatorname{\mathfrak{B}}$ has a binary injective polymorphism. By Lemma
4.3 the relation algebra $\operatorname{\mathbf{A}}$ has all $1$-cycles. We
apply Theorem 4.4 and get that the second item in Theorem 5.2 holds.

We prove the converse implication by showing the contraposition. Assume that
the first item is not satisfied. Then Theorem 9.1 in [BK22] implies that there
exists a polynomial-time reduction from $\operatorname{CSP}(K_{3})$ to
$\operatorname{NSP}(\mathbf{A})$ which preserves solvability by the
$(k,l)$-consistency procedure. The problem $\operatorname{CSP}(K_{3})$ is the
3-colorability problem which is known (e.g., by [BK09]) to be not solvable by
the $(k,l)$-consistency procedure for every $k,l\in\mathbb{N}$. Hence
$\operatorname{NSP}(\mathbf{A})$ cannot be solved by the $(4,6)$-consistency
procedure. ∎

As a consequence of Theorem 5.2 we obtain the following strengthening of the
complexity dichotomy NSPs of finite symmetric integral relation algebra with a
flexible atom [BK22].

######  Corollary 5.3 (Complexity Dichotomy).

Let $\operatorname{\mathbf{A}}$ be a finite symmetric integral relation
algebra with a flexible atom. Then
$\operatorname{NSP}(\operatorname{\mathbf{A}})$ can be solved by the
$(4,6)$-consistency procedure, or it is NP-complete.

###### Proof.

Suppose that the first condition in Theorem 5.2 holds. Then Theorem 5.2
implies that $\operatorname{NSP}(\operatorname{\mathbf{A}})$ can be solved by
the $(4,6)$-consistency procedure. If the first condition in Theorem 5.2 is
not satisfied it follows from Theorem 9.1. in [BK22] that
$\operatorname{NSP}(\operatorname{\mathbf{A}})$ is NP-complete. ∎

##  6 The Complexity of the Meta Problem

In this section we study the computational complexity of deciding for a given
finite symmetric relation algebra ${\bf A}$ with a flexible atom whether the
$k$-consistency algorithm solves $\operatorname{NSP}({\bf A})$. We show that
this problem is decidable in polynomial time even if ${\bf A}$ is given by the
restriction of its composition table to the atoms of ${\bf A}$: note that this
determines a symmetric relation algebra uniquely, and that this is an
(exponentially) more succinct representation of ${\bf A}$ compared to
explicitly storing the full composition table.

######  Definition 6.1 (Meta Problem).

We define $\operatorname{Meta}$ as the following computational problem.
Input: the composition table of a finite symmetric relation algebra ${\bf A}$
restricted to $A_{0}$.
Question: is there a $k\in{\mathbb{N}}$ such that $k$-consistency solves
$\operatorname{NSP}({\bf A})$?

Our proof of Theorem 3.2 shows that $\operatorname{Meta}$ is undecidable as
well. The proof of the following theorem can be found in Appendix C.

######  Theorem 6.2.

$\operatorname{Meta}$ can be decided in polynomial time if the input is
restricted to finite symmetric integral relation algebras ${\bf A}$ with a
flexible atom.

##  7 Conclusion and Open Questions

The question whether the network satisfaction problem for a given finite
relation algebra can be solved by the famous $k$-consistency procedure is
undecidable. Our proof of this fact heavily relies on prior work of Hirsch
[Hir99] and of Hirsch and Hodkinson [HH01a] and shows that almost any question
about the network satisfaction problem for finite relation algebras is
undecidable.

However, if we further restrict the class of finite relation algebras, one may
obtain strong classification results. We have demonstrated this for the class
of finite symmetric integral relation algebras with a flexible atom (Theorem
5.3); the complexity of deciding whether the conditions in our classification
result hold drops from undecidable to P (Theorem 6.2). One of the remaining
open problems is a characterisation of the power of $k$-consistency for the
larger class of all finite relation algebras with a normal representation.

Our main result (Theorem 4.4) is a sufficient condition for the applicability
of the $k$-consistency procedure; the condition does not require the existence
of a flexible atom but applies more generally to finite symmetric relation
algebras $\bf A$ with a normal representation. Our condition consists of two
parts: the first is the existence of all 1-cycles in $\bf A$, the second is
that $\bf A$ admits a Siggers behavior. We conjecture that dropping the first
part of the condition leads to a necessary and sufficient condition for
solvability by the $k$-consistency procedure.

######  Conjecture 7.1.

A finite symmetric relation algebra $\bf A$ with a normal representation
admits a Siggers behavior if and only if $\operatorname{NSP}(\mathbf{A})$ can
be solved by the $k$-consistency procedure for some $k\in\mathbb{N}$.

Note that this conjecture generalises Theorem 5.2. Both directions of the
conjecture are open. However, the forward direction of the conjecture is true
if ${\bf A}$ has a normal representation with a primitive automorphism group:
in this case, it is known that a Siggers behavior implies the existence of all
1-cycles [BK20], and hence the claim follows from our main result (Theorem
5.2). The following example shows a finite symmetric relation algebra $\bf A$
which does not have all 1-cycles and an imprimitive normal representation, but
still $\operatorname{NSP}({\bf A})$ can be solved by the $k$-consistency
procedure for some $k\in\mathbb{N}$.

$~{}\circ~{}$ | $~{}\operatorname{Id}~{}$ | $E$ | $N$
---|---|---|---
$\operatorname{Id}$ | $\operatorname{Id}$ | $E$ | $N$
$E$ | $E$ | $\operatorname{Id}$ | $N$
$N$ | $N$ | $N$ | $1$
Figure 2: Multiplication table of the relation algebra $\mathbf{C}$.

######  Example 7.2.

Theorem 4.4 is a sufficient condition for the NSP of a relation algebra
$\operatorname{\mathbf{A}}$ to be solved by the $k$-consistency procedure for
some $k\in\mathbb{N}$. However, there exists a finite symmetric relation
algebra $\operatorname{\mathbf{C}}$ such that $\operatorname{NSP}(\mathbf{C})$
is solved by the $2$-consistency procedure, but we cannot prove this by the
methods used to obtain Theorem 4.4. Consider the relation algebra $\mathbf{C}$
with atoms $\\{\operatorname{Id},E,N\\}$ and the multiplication table in
Figure 2. This relation algebra has a normal representation, namely the
expansion of the infinite disjoint union of the clique $K_{2}$ by all first-
order definable binary relations. We denote this structure by
$\overline{\omega K_{2}}$. One can observe that
$\operatorname{CSP}(\overline{\omega K_{2}})$ and therefore also the NSP of
the relation algebra can be solved by the $(2,3)$-consistency algorithm (for
details see [Knä23]).

The relation algebra $\mathbf{C}$ does not have all $1$-cycles and therefore
does not fall into the scope of Theorem 4.4. In fact, our proof of Theorem
does not work for $\mathbf{C}$, because the CSP of the atom structure
$\operatorname{\mathfrak{C}}_{0}$ of $\operatorname{\mathbf{C}}$ cannot be
solved by the $k$-consistency procedure for some $k\in\mathbb{N}$. Hence, the
reduction of $\operatorname{NSP}(\mathbf{C})$ to
$\operatorname{CSP}(\operatorname{\mathfrak{C}}_{0})$ (incorporated in Theorem
2.23) does not imply that $\operatorname{NSP}(\mathbf{C})$ can be solved by
$k$-consistency procedure for some $k\in\mathbb{N}$.

The following problems are still open and are relevant for resolving
Conjecture 7.1.

  * •

Show Conjecture 7.1 if the normal representation of ${\bf A}$ has a primitive
automorphism group.

  * •

Characterise the power of the $k$-consistency procedure for the NSP of finite
relation algebras with a normal representation whose automorphism group is
imprimitive. In this case, there is a non-trivial definable equivalence
relation. It is already known that if this equivalence relation has finitely
many classes, then the NSP is NP-complete and the $k$-consistency procedure
does not solve the NSP [BK20]. Similarly, the NSP is NP-complete if there are
equivalence classes of finite size larger than two. It therefore remains to
study the case of infinitely many two-element classes, and with infinitely
many infinite classes. In both cases we wish to reduce the classification to
the situation with a primitive automorphism group.

Finally, we ask whether it is true that if $\bf A$ is a finite symmetric
relation algebra with a flexible atom and $\operatorname{NSP}(\bf A)$ can be
solved by the $k$-consistency procedure for some $k$, then it can also be
solved by the $(2,3)$-consistency procedure? In other words, improve $(4,6)$
in Corollary 5.3 to $(2,3)$.

## References

  * [ABD07] Albert Atserias, Andrei A. Bulatov, and Víctor Dalmau.  On the power of $k$-consistency.  In ICALP, pages 279–290, 2007.
  * [AMM08] Jeremy F. Alm, Roger D. Maddux, and Jacob Manske.  Chromatic graphs, Ramsey numbers and the flexible atom conjecture.  The Electronic Journal of Combinatorics, 15(1), March 2008.
  * [Bar11] Libor Barto.  The dichotomy for conservative constraint satisfaction problems revisited.  In Proceedings of the Symposium on Logic in Computer Science (LICS), Toronto, Canada, 2011.
  * [BD13] Manuel Bodirsky and Víctor Dalmau.  Datalog and constraint satisfaction with infinite templates.  Journal on Computer and System Sciences, 79:79–100, 2013.  A preliminary version appeared in the proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS’05).
  * [BJ17] Manuel Bodirsky and Peter Jonsson.  A model-theoretic view on qualitative constraint reasoning.  Journal of Artificial Intelligence Research, 58:339–385, 2017.
  * [BK09] Libor Barto and Marcin Kozik.  Constraint satisfaction problems of bounded width.  In Proceedings of Symposium on Foundations of Computer Science (FOCS), pages 595–603, 2009.
  * [BK14] Libor Barto and Marcin Kozik.  Constraint satisfaction problems solvable by local consistency methods.  Journal of the ACM, 61(1):3:1–3:19, 2014.
  * [BK20] Manuel Bodirsky and Simon Knäuer.  Hardness of network satisfaction for relation algebras with normal representations.  In Relational and Algebraic Methods in Computer Science, pages 31–46. Springer International Publishing, 2020.
  * [BK21] Manuel Bodirsky and Simon Knäuer.  Network satisfaction for symmetric relation algebras with a flexible atom.  In Proceedings of AAAI, 2021.  Preprint https://arxiv.org/abs/2008.11943.
  * [BK22] Manuel Bodirsky and Simon Knäuer.  The complexity of network satisfaction problems for symmetric relation algebras with a flexible atom.  Journal of Artificial Intelligence Research, 75:1701–1744, December 2022.
  * [BKKR69] V. G. Bodnarčuk, L. A. Kalužnin, V. N. Kotov, and B. A. Romov.  Galois theory for Post algebras, part I and II.  Cybernetics, 5:243–539, 1969.
  * [BM18] Manuel Bodirsky and Antoine Mottet.  A dichotomy for first-order reducts of unary structures.  Logical Methods in Computer Science, 14(2), 2018.
  * [Bod12] Manuel Bodirsky.  Complexity classification in infinite-domain constraint satisfaction.  Mémoire d’habilitation à diriger des recherches, Université Diderot – Paris 7. Available at arXiv:1201.0856v8, 2012.
  * [Bod18] Manuel Bodirsky.  Finite relation algebras with normal representations.  In Relational and Algebraic Methods in Computer Science - 17th International Conference, RAMiCS 2018, Groningen, The Netherlands, October 29 \- November 1, 2018, Proceedings, pages 3–17, 2018.
  * [Bul03] Andrei A. Bulatov.  Tractable conservative constraint satisfaction problems.  In Proceedings of the Symposium on Logic in Computer Science (LICS), pages 321–330, Ottawa, Canada, 2003.
  * [Bul11] Andrei A. Bulatov.  Complexity of conservative constraint satisfaction problems.  ACM Trans. Comput. Logic, 12(4), jul 2011.
  * [Bul16] Andrei A. Bulatov.  Conservative constraint satisfaction re-revisited.  Journal Computer and System Sciences, 82(2):347–356, 2016.  ArXiv:1408.3690.
  * [Bul17] Andrei A. Bulatov.  A dichotomy theorem for nonuniform CSPs.  In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, pages 319–330, 2017.
  * [CH04] Matteo Cristiani and Robin Hirsch.  The complexity of the constraint satisfaction problem for small relation algebras.  Artificial Intelligence Journal, 156:177–196, 2004.
  * [CL17] Hubie Chen and Benoît Larose.  Asking the metaquestions in constraint tractability.  TOCT, 9(3):11:1–11:27, 2017.
  * [Dün05] Ivo Düntsch.  Relation algebras and their application in temporal and spatial reasoning.  Artificial Intelligence Review, 23:315–357, 2005.
  * [FV99] Tomás Feder and Moshe Y. Vardi.  The computational structure of monotone monadic SNP and constraint satisfaction: a study through Datalog and group theory.  SIAM Journal on Computing, 28:57–104, 1999.
  * [Gei68] David Geiger.  Closed systems of functions and predicates.  Pacific Journal of Mathematics, 27:95–100, 1968.
  * [HH01a] R. Hirsch and I. Hodkinson.  Representability is not decidable for finite relation algebras.  Transactions of the American Mathematical Society, 353(4):1387–1401), 2001.
  * [HH01b] R. Hirsch and I. Hodkinson.  Strongly representable atom structures of relation algebras.  Transactions of the American Mathematical Society, 130(6):1819–1831), 2001.
  * [HH02] Robin Hirsch and Ian Hodkinson.  Relation Algebras by Games.  North Holland, 2002.
  * [Hir96] Robin Hirsch.  Relation algebras of intervals.  Artificial Intelligence Journal, 83:1–29, 1996.
  * [Hir97] Robin Hirsch.  Expressive power and complexity in algebraic logic.  Journal of Logic and Computation, 7(3):309 – 351, 1997.
  * [Hir99] Robin Hirsch.  A finite relation algebra with undecidable network satisfaction problem.  Logic Journal of the IGPL, 7(4):547–554, 1999.
  * [Kaz15] Alexandr Kazda.  CSP for binary conservative relational structures.  Algebra universalis, 75(1):75–84, December 2015.
  * [KKVW15] Marcin Kozik, Andrei Krokhin, Matt Valeriote, and Ross Willard.  Characterizations of several Maltsev conditions.  Algebra universalis, 73(3):205–224, 2015.
  * [Knä23] Simon Knäuer.  Constraint Network Satisfaction for Finite Relation Algebras.  PhD thesis, Technische Universität Dresden, 2023.
  * [Lyn50] R. Lyndon.  The representation of relational algebras.  Annals of Mathematics, 51(3):707–729, 1950.
  * [Mad94] Roger D. Maddux.  A perspective on the theory of relation algebras.  Algebra Universalis, 31(3):456–465, September 1994.
  * [Mad06] Roger D. Maddux.  Relation Algebras: Volume 150.  Studies in logic and the foundations of mathematics. Elsevier Science, London, England, May 2006.
  * [McK66] Ralph McKenzie.  The representation of relation algebras.  PhD thesis, University of Colorado at Boulder, 1966.
  * [McK70] Ralph McKenzie.  Representations of integral relation algebras.  Michigan Mathematical Journal, 17(3):279 – 287, 1970.
  * [MNPW21] Antoine Mottet, Tomás Nagy, Michael Pinsker, and Michal Wrona.  Smooth approximations and relational width collapses.  In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12-16, 2021, Glasgow, Scotland (Virtual Conference), volume 198 of LIPIcs, pages 138:1–138:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
  * [RN07] Jochen Renz and Bernhard Nebel.  Qualitative spatial reasoning using constraint calculi.  In M. Aiello, I. Pratt-Hartmann, and J. van Benthem, editors, Handbook of Spatial Logics, pages 161–215. Springer Verlag, Berlin, 2007.
  * [Tar48] Alfred Tarski.  Representation problems for relation algebras.  Bulletin of the AMS, 54(80), 1948.
  * [Zhu17] Dmitriy N. Zhuk.  A proof of CSP dichotomy conjecture.  In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, pages 331–342, 2017.  https://arxiv.org/abs/1704.01914.
  * [Zhu20] Dmitriy Zhuk.  A proof of the CSP dichotomy conjecture.  J. ACM, 67(5):30:1–30:78, 2020.

##  Appendix A Preliminaries

###  A.1 The Network Satisfaction Problem

See 2.9

###### Proof.

The first item can be checked by a straightforward calculation. For the second
item note that elements of
$\operatorname{\mathbf{A}}_{1}\times\operatorname{\mathbf{A}}_{2}$ are pairs
$(a_{1},a_{2})\in A_{1}\times A_{2}$. Since $\operatorname{\mathfrak{B}}$ is a
representation of
$\operatorname{\mathbf{A}}_{1}\times\operatorname{\mathbf{A}}_{2}$, there
exists for every $(a_{1},a_{2})\in A_{1}\times A_{2}$ a binary relation
$(a_{1},a_{2})^{\operatorname{\mathfrak{B}}}$. For better readability, we
denote constants of relation algebras by the signature elements
$\\{0,1,\operatorname{Id}\\}$ (without the superscipt). It will always be
clear from the context which algebra is meant. For example, $(0,1)\in
A_{1}\times A_{2}$ is meant to be the element
$(0^{\operatorname{\mathbf{A}}_{1}},1^{\operatorname{\mathbf{A}}_{2}})$ of the
algebra $\operatorname{\mathbf{A}}_{1}\times\operatorname{\mathbf{A}}_{2}$.

Consider the sets

$\displaystyle B_{1}$ $\displaystyle:=\\{x\in
B\mid(x,x)\in(1,0)^{\operatorname{\mathfrak{B}}}\\}$ $\displaystyle\text{ and
}B_{2}$ $\displaystyle:=\\{x\in
B\mid(x,x)\in(0,1)^{\operatorname{\mathfrak{B}}}\\}.$

We claim that $\\{B_{1},B_{2}\\}$ forms a partition of $B$. Clearly,
$B_{1}\cup B_{2}=B$, because

$\\{(x,x)\mid x\in
B\\}=(\operatorname{Id},\operatorname{Id})^{\operatorname{\mathfrak{B}}}\subseteq((1,0)^{\operatorname{\mathfrak{B}}}\cup(0,1)^{\operatorname{\mathfrak{B}}}).$

By the definition of the relation algebra
$\operatorname{\mathbf{A}}_{1}\times\operatorname{\mathbf{A}}_{2}$ it holds
that
$(0,0)=(1,0)\cap^{\operatorname{\mathbf{A}}_{1}\times\operatorname{\mathbf{A}}_{2}}(0,1)$.
Since $\operatorname{\mathfrak{B}}$ is a representation of
$\operatorname{\mathbf{A}}_{1}\times\operatorname{\mathbf{A}}_{2}$ we have
$\emptyset=(0,0)^{\operatorname{\mathfrak{B}}}=(1,0)^{\operatorname{\mathfrak{B}}}\cap(0,1)^{\operatorname{\mathfrak{B}}}$
and
$B=(1,1)^{\operatorname{\mathfrak{B}}}=(1,0)^{\operatorname{\mathfrak{B}}}\cup(0,1)^{\operatorname{\mathfrak{B}}}$
and it follows that $\emptyset=B_{1}\cap B_{2}$ and $B=B_{1}\cup B_{2}$.
Hence, $\\{B_{1},B_{2}\\}$ is a partition of $B$.

Furthermore, we claim that there is no pair $(x,y)\in B_{1}\times B_{2}$ in
any relation
$(a_{1},a_{2})^{\operatorname{\mathfrak{B}}}\subseteq(1,1)^{\operatorname{\mathfrak{B}}}$
of $\operatorname{\mathfrak{B}}$. So see this, note that for a tuple $(x,y)\in
B_{1}\times B_{2}$ with $(x,y)\in(1,1)^{\operatorname{\mathfrak{B}}}$ it
follows from the definition of the relational product $\circ$ that
$\\{(x,y)\\}=(\\{(x,x)\\}\circ\\{(x,y)\\})\circ\\{(y,y)\\}$ and therefore
$(x,y)\in((1,0)^{\operatorname{\mathfrak{B}}}\circ(1,1)^{\operatorname{\mathfrak{B}}})\circ(0,1)^{\operatorname{\mathfrak{B}}}$
holds. Since this contradicts
$\emptyset=(0,0)^{\operatorname{\mathfrak{B}}}=((1,0)^{\operatorname{\mathfrak{B}}}\circ(1,1)^{\operatorname{\mathfrak{B}}})\circ(0,1)^{\operatorname{\mathfrak{B}}}$,
there is no pair $(x,y)\in B_{1}\times B_{2}$ in any relation
$(a_{1},a_{2})^{\operatorname{\mathfrak{B}}}\subseteq(1,1)^{\operatorname{\mathfrak{B}}}$.

Altogether we observe that $B_{1}$ is the domain of an
$(A_{1}\times\\{0\\})$-structure $\operatorname{\mathfrak{B}}_{1}$ with
$(a,0)^{\operatorname{\mathfrak{B}}_{1}}:=(a,0)^{\operatorname{\mathfrak{B}}}$
for every $a\in A_{1}$. Analogously, the $(\\{0\\}\times A_{2})$-structure
$\operatorname{\mathfrak{B}}_{2}$ is defined by
$(0,a)^{\operatorname{\mathfrak{B}}_{2}}:=(0,a)^{\operatorname{\mathfrak{B}}}$
for every $a\in A_{2}$. One can check that the mapping
$a\mapsto(a,0)^{\operatorname{\mathfrak{B}}_{1}}$ is indeed an isomorphism
that witnesses that $\operatorname{\mathbf{A}}_{1}$ has the representation
$\operatorname{\mathfrak{B}}_{1}$. Analogously, we get that
$a\mapsto(0,a)^{\operatorname{\mathfrak{B}}}$ witnesses that
$\operatorname{\mathbf{A}}_{2}$ has the representation
$\operatorname{\mathfrak{B}}_{2}$. ∎

###  A.2 The Universal-Algebraic Approach

####  A.2.1 Conservative Clones

According to Definition 2.18, an “edge type” of a concrete set
$\\{a,b\\}\subseteq B$ is witnessed by a certain operation. For another set
$\\{c,d\\}\subseteq B$ this could a priori be a different operation (even if
the two sets have the same edge type). However, Bulatov obtained “uniform
witness operations” by the following proposition.

######  Proposition A.1 (Proposition 3.1.in [Bul11]).

Let $\operatorname{\mathfrak{B}}$ be a finite structure. Then there are a
binary operation $v\in\operatorname{Pol}(\operatorname{\mathfrak{B}})$ and
ternary operations $g,h\in\operatorname{Pol}(\operatorname{\mathfrak{B}})$
such that for every two-element subset $C$ of $B$ we have that

  * •

$v|_{C}$ is a semilattice operation whenever $C$ has a semilattice edge, and
$v|_{C}(x,y)=x$ otherwise;

  * •

$g|_{C}$ is a majority operation if $C$ is a majority edge, $g|_{C}(x,y,z)=x$
if $C$ is affine and $g|_{C}(x,y,z)=v|_{C}(v|_{C}(x,y),z)$ if $C$ has a
semilattice edge;

  * •

$h|_{C}$ is a minority operation if $C$ is an affine edge, $h|_{C}(x,y,z)=x$
if $C$ is majority and $h|_{C}(x,y,z)=v|_{C}(v|_{C}(x,y),z)$ if $C$ has a
semilattice edge.

##  Appendix B Tractability via $k$-Consistency

###  B.1 The Atom Structure

For the sake of notation, we make some global assumptions for Sections
B.1-B.3. Let $\operatorname{\mathbf{A}}$ be a finite relation algebra that
satisfies the assumptions from Theorem 4.4. We denote by
$\operatorname{\mathfrak{A}_{0}}$ the atom structure of
$\operatorname{\mathbf{A}}$ (Definition 2.15). Since
$\operatorname{\mathbf{A}}$ is a symmetric relation algebra, the relation
$R^{\operatorname{\mathfrak{A}}_{0}}$ is totally symmetric. Furthermore, we
can drop the binary relation $E^{\operatorname{\mathfrak{A}}_{0}}$, since it
consists only of loops and does not change the set of polymorphisms. Let
$s\in\operatorname{Pol}(\operatorname{\mathfrak{A}_{0}})$ be the Siggers
operation that exists by the assumptions in Theorem 4.4. This implies by
Theorem 2.19 for every $a,b\in A_{0}$ that the set $\\{a,b\\}$ is a majority
edge or an affine edge, or that there is a semilattice edge on $\\{a,b\\}$.
The different types of edges are witnessed by certain operations that we get
from Proposition A.1: there exist a binary operation
$f\in\operatorname{Pol}(\operatorname{\mathfrak{A}_{0}})$ and ternary
operations $g,h\in\operatorname{Pol}(\operatorname{\mathfrak{A}_{0}})$ such
that for every two element subset $C$ of $A_{0}$,

  * •

$f|_{C}$ is a semilattice operation whenever $C$ has a semilattice edge, and
$f|_{C}(x,y)=x$ otherwise;

  * •

$g|_{C}$ is a majority operation if $C$ is a majority edge, $g|_{C}(x,y,z)=x$
if $C$ is affine and $g|_{C}(x,y,z)=f|_{C}(f|_{C}(x,y),z)$ if $C$ has a
semilattice edge;

  * •

$h|_{C}$ is a minority operation if $C$ is an affine edge, $h|_{C}(x,y,z)=x$
if $C$ is majority and $h|_{B}(x,y,z)=f|_{C}(f|_{C}(x,y),z)$ if $C$ has a
semilattice edge.

We will fix these operations and introduce the following terminology. A tuple
$(a,b)\in A_{0}$ is called _$f$ -sl_ if $f(a,b)=b=f(b,a)$ holds. Next, we
prove several important properties of the relation $R$: that it must contain
certain triples (Lemma B.1), that it must not contain certain other triples
(Lemma B.2), and that it is affected by the presence of semilattice edges in
$\operatorname{\mathbf{A}}_{0}$ (Lemma B.3 and Lemma B.4).

######  Lemma B.1.

The relation $R$ of the atom structure $\operatorname{\mathfrak{A}_{0}}$ has
the following properties:

  * •

for all $a\in A_{0}$ we have $(a,a,a)\in R$.

  * •

for all $a,b\in A_{0}$ we have $(a,a,b)\in R$ or $(a,b,b)\in R$;

###### Proof.

The first item follows from the assumption that $\operatorname{\mathbf{A}}$
has all 1-cycles.

For the second item observe that $\\{a,\operatorname{Id}\\}$ cannot be a
majority edge. Otherwise,

$g((a,a,\operatorname{Id}),(\operatorname{Id},a,a),(\operatorname{Id},\operatorname{Id},\operatorname{Id}))=(\operatorname{Id},a,\operatorname{Id})\in
R$

is a contradiction to the properties of $\operatorname{Id}$. Furthermore,
$(a,\operatorname{Id})$ cannot be $f$-sl, since

$f((a,a,\operatorname{Id}),(\operatorname{Id},a,a))=(\operatorname{Id},a,\operatorname{Id})\in
R.$

This is again a contradiction. Since these observations also hold for $b$
instead of $a$ we have the following case distinction.

  1. 1.

$(\operatorname{Id},a)$ is $f$-sl and $(\operatorname{Id},b)$ is $f$-sl. It
follows that
$f((a,a,\operatorname{Id}),(\operatorname{Id},b,b))\in\\{(a,a,b),(a,b,b)\\}$.
Since $f$ preserves $R$, $(a,a,\operatorname{Id})\in R$, and
$(\operatorname{Id},b,b)\in R$ we get that
$f((a,a,\operatorname{Id}),(\operatorname{Id},b,b))\in R$. This implies that
$(a,a,b)\in R$ or $(a,b,b)\in R$.

  2. 2.

$(\operatorname{Id},a)$ is $f$-sl and $\\{b,\operatorname{Id}\\}$ is affine.
By the definition of $f$ we get
$f((b,b,\operatorname{Id}),(\operatorname{Id},a,a))\in\\{(b,a,a),(b,b,a)\\}$.
By the same argument as in Case 1 we get that $(a,a,b)\in R$ or $(a,b,b)\in
R$.

  3. 3.

$(\operatorname{Id},b)$ is $f$-sl and $\\{a,\operatorname{Id}\\}$ is affine.
This case is analogous to Case 2.

  4. 4.

$\\{a,\operatorname{Id}\\}$ is affine and $\\{b,\operatorname{Id}\\}$ is
affine. Observe that

$g((a,\operatorname{Id},a),(\operatorname{Id},b,b),(\operatorname{Id},\operatorname{Id},\operatorname{Id}))\in\\{(a,b,a),(a,b,b)\\},$

since $g(a,b,\operatorname{Id})\in\\{a,b,\operatorname{Id}\\}$ and the triple
$(a,b,\operatorname{Id})$ is forbidden. As in the cases before it follows that
$(a,a,b)\in R$ or $(a,b,b)\in R$.

This concludes the proof of the second item. ∎

$a$$b$$c$$\Rightarrow$ | $a$$b$$c$
---|---
Figure 3: The statement of Lemma B.2. The red shape means $(a,b,c)\notin R$,
the black arrow means $(a,a,b)\notin R$.

######  Lemma B.2.

Let $a,b,c\in A_{0}$ be such that $(a,b,c)\notin R$ and $|\\{a,b,c\\}|=3$.
Then there are $x,y\in\\{a,b,c\\}$ such that $(x,x,y)\notin R$.

###### Proof.

We first suppose that there is a semilattice edge on $\\{a,b,c\\}$. Without
loss of generality we assume that $(a,b)$ is $f$-sl. If $f(c,a)=c$ then
$(a,a,c)\notin R$ or $(b,a,a)\notin R$ because otherwise

$f((a,a,c),(b,a,a))=(b,a,c)\in R$

contradicting our assumption. If $f(c,a)=a$ then $(b,c,c)\notin R$ or
$(a,a,c)\notin R$ because otherwise

$f((b,c,c),(a,a,c))=(b,a,c)\in R$

which is again a contradiction. Hence, in all the cases we found
$x,y\in\\{a,b,c\\}$ such that $(x,x,y)\notin R$ and are done. In the following
we therefore assume that there is no semilattice edge on $\\{a,b,c\\}$.

Next we suppose that there is an affine edge on $\\{a,b,c\\}$. Without loss of
generality we assume that $\\{a,b\\}$ is an affine edge. Since there are no
semilattice edges on $\\{a,b,c\\}$ we distinguish the following two cases:

  1. 1.

$\\{a,c\\}$ is an affine edge. In this case $(c,a,a)\notin R$ or
$(a,b,a)\notin R$ because otherwise

$h((c,a,a),(a,a,a),(a,b,a))=(c,b,a)\in R.$

  2. 2.

$\\{a,c\\}$ is a majority edge. In this case $(a,a,c)\notin R$ or
$(a,b,a)\notin R$ or $(b,b,c)\notin R$, because otherwise

$h((a,a,c),(a,b,a),(b,b,c))=(b,a,c)\in R.$

In both cases we again found $x,y\in\\{a,b,c\\}$ such that $(x,x,y)\notin R$
and are done. We therefore suppose in the following that there are no affine
edges on $\\{a,b,c\\}$. Hence, all edges on $\\{a,b,c\\}$ are majority edges.
Then $(a,a,c)\notin R$ or $(a,b,a)\notin R$ or $(b,b,c)\notin R$ because
otherwise

$g((a,a,c),(a,b,a),(b,b,c))=(a,b,c)\in R.$

Thus, also in this case we found $x,y\in\\{a,b,c\\}$ such that $(x,x,y)\notin
R$. ∎

The next lemma states that the edge type on $\\{a,b\\}$ is predetermined
whenever a triple $(a,a,b)$ is not in $R$.

######  Lemma B.3.

Let $a,b\in A_{0}$ be such that $(a,a,b)\notin R$. Then $(a,b)$ is a
semilattice edge in $\operatorname{\mathfrak{A}_{0}}$ but $(b,a)$ is not.

###### Proof.

By Lemma B.1 we know that $(a,b,b)\in R$, $(a,a,a)\in R$, and $(b,b,b)\in R$.
Assume for contradiction that $\\{a,b\\}$ is a majority edge. Then

$g((a,a,a),(a,b,b),(b,b,a))=(a,b,a)$

which contradicts the fact that $g$ preserves $R$. Assume next that
$\\{a,b\\}$ is an affine edge. Then

$h((a,b,b),(b,a,b),(b,b,b))=(a,a,b)$

which again contradicts the fact that $h$ preserves $R$. Finally, if $(b,a)$
is a semilattice edge then

$f((a,b,b),(b,a,b))=(a,a,b)$

which contradicts the assumption that $f$ preserves $R$. If follows that
$(a,b)$ is the only semilattice edge on $\\{a,b\\}$ and therefore
$f(a,b)=b=f(b,a)$ holds. ∎

$a$$a^{\prime}$$b$$c$$\Rightarrow$ | $a$$a^{\prime}$$b$$c$$\times$
---|---
Figure 4: The statement of Lemma B.4. The blue shape means
$(a^{\prime},b,c)\in R$, the crossed-out red arrow means $(a^{\prime},a)$ is
not a semilattice edge.

######  Lemma B.4.

Let $a,a^{\prime},b,c\in A_{0}$ be such that $(a,b,c)\notin R$, $(a,a,b)\notin
R$, and $(a^{\prime},b,c)\in R$. Then $(a^{\prime},a)$ is not a semilattice
edge.

###### Proof.

Assume for contradiction $(a^{\prime},a)$ is a semilattice edge, i.e., there
exists $p\in\operatorname{Pol}(\mathfrak{A}_{0})$ with
$p(a,a^{\prime})=a=p(a^{\prime},a)$. Note that by Lemma B.1 it follows that
$(a,a,a)\in R$ and $(a,b,b)\in R$.

Claim 1: $p(b,a)=a$ implies $p(a,b)=b$. This follows immediately, since
otherwise
$p((a,b,b),(b,a,b))=(a,a,b)\in R$ is a contradiction.

Claim 2: $(a,a,c)\not\in R$. We assume the opposite and consider the only two
possible cases for $p(b,a)$.

  1. 1.

$p(b,a)=b$: We get a contradiction by $p((a^{\prime},b,c),(a,a,c))=(a,b,c)\in
R$.

  2. 2.

$p(b,a)=a$: By Claim 1 we know that $p(a,b)=b$ follows. Then
$p((a,a,c),(a^{\prime},b,c))=(a,b,c)\in R$ contrary to our assumptions.

This proves Claim 2.

Claim 3: $p(c,a)=a$ implies $p(a,c)=c$. Lemma B.1 together with Claim 2
implies that $(a,c,c)\in R$. Now Claim 3 follows immediately, since otherwise
$p((a,c,c),(c,a,c))=(a,a,c)\in R$, which contradicts Claim 2.

We finally make a case distinction for all possible values of $p$ on $(b,a)$
and $(c,a)$.

  1. 1.

$p(b,a)=b$ and $p(c,a)=c$: We get a contradiction by
$p((a^{\prime},b,c),(a,a,a))=(a,b,c)\in R$.

  2. 2.

$p(b,a)=b$ and $p(c,a)=a$: We get a contradiction by
$p((a^{\prime},b,c),(a,a,a))=(a,b,a)\in R$.

  3. 3.

$p(b,a)=a$ and $p(c,a)=c$: $p((a^{\prime},b,c),(a,a,a))=(a,a,c)\in R$
contradicts Claim 2.

  4. 4.

$p(b,a)=a$ and $p(c,a)=a$: By Claim 1 we get $p(a,b)=b$ and by Claim 3 we get
$p(a,c)=c$. This yields a contradiction by
$p((a,a,a),(a^{\prime},b,c))=(a,b,c)\in R$.

This proves the lemma. ∎

###  B.2 The Binarisation

We have announced in the introduction that we want to apply Kazda’s theorem
(Theorem 4.6) for binary conservative structures, but the atom structure
$\operatorname{\mathfrak{A}_{0}}$ from Section B.1 has a ternary relation. We
therefore associate a certain binary structure
$\operatorname{\mathfrak{A}^{b}_{0}}$ to $\operatorname{\mathfrak{A}_{0}}$
which shares many properties with $\operatorname{\mathfrak{A}_{0}}$.

######  Definition B.5.

We denote by $\operatorname{\mathfrak{A}^{b}_{0}}$ the structure with domain
$A_{0}$ and the following relations:

  * •

a unary relation $U_{S}$ for each subset $S$ of $A_{0}$;

  * •

for every $a\in A_{0}$ the binary relation $R_{a}:=\\{(x,y)\in
A_{0}^{2}\mid(a,x,y)\in R\\}$;

  * •

a relation for every union of relations of the form $R_{a}$.

The binarisation of $\operatorname{\mathfrak{A}_{0}}$ according to Definition
B.5 will be denoted by $\operatorname{\mathfrak{A}^{b}_{0}}$. We obtain the
following results about the relationship of
$\operatorname{Pol}(\operatorname{\mathfrak{A}_{0}})$ and
$\operatorname{Pol}(\operatorname{\mathfrak{A}^{b}_{0}})$.

######  Lemma B.6.

$\operatorname{Pol}(\mathfrak{A}_{0})\subseteq\operatorname{Pol}(\mathfrak{A}_{0}^{b})$.

###### Proof.

Clearly, every relation $R_{a}$ has the primitive positive definition $\exists
z(U_{\\{a\\}}(z)\wedge R(z,x,y))$ in $\operatorname{\mathfrak{A}_{0}}$. A
primitive positive definition of $\cup_{a\in S}R_{a}$ is $\exists
z(U_{S}(z)\wedge R(z,x,y))$ in $\operatorname{\mathfrak{A}_{0}}$. Then the
statement of the lemma follows by Theorem 2.14. ∎

######  Lemma B.7.

$\operatorname{Pol}^{(2)}(\mathfrak{A}_{0}^{b})\subseteq\operatorname{Pol}^{(2)}(\mathfrak{A}_{0})$.

###### Proof.

Let $f\in\operatorname{Pol}^{(2)}(\operatorname{\mathfrak{A}^{b}_{0}})$. It
suffices to prove that $f$ preserves the relation
$R^{\operatorname{\mathfrak{A}}_{0}}$. Arbitrarily choose
$(a_{1},b_{1},c_{1}),(a_{2},b_{2},c_{2})\in R$. We want to show that
$t:=(f(a_{1},a_{2}),f(b_{1},b_{2}),f(c_{1},c_{2}))$ is in $R$ as well. If
$t\in\\{(a_{1},b_{1},c_{1}),(a_{2},b_{2},c_{2})\\}$ then there is nothing to
be shown. Otherwise, since $f$ must preserve $\\{a_{1},a_{2}\\}$,
$\\{b_{1},b_{2}\\}$, and $\\{c_{1},c_{2}\\}$, by the symmetry of $R$ and
possibly flipping the arguments of $f$ we may assume without loss of
generality that $f(a_{1},a_{2})=a_{1}$, $f(b_{1},b_{2})=b_{1}$, and
$f(c_{1},c_{2})=c_{2}$. So we have to show that $t=(a_{1},b_{1},c_{2})\in R$.
Note that $(b_{1},c_{1})\in R_{a_{1}}$ and $(b_{2},c_{2})\in R_{a_{2}}$, and
therefore $(f(b_{1},b_{2}),f(c_{1},c_{2}))\in R_{a_{1}}\cup R_{a_{2}}$. In the
first case, we obtain that $(b_{1},c_{2})\in R_{a_{1}}$, and hence
$(a_{1},b_{1},c_{2})\in R$ and we are done. In the second case, we obtain that
$(b_{1},c_{2})\in R_{a_{2}}$, and hence $(a_{2},b_{1},c_{2})\in R$. In
partciular, $(a_{2},c_{2})\in R_{b_{1}}$. Since $(a_{1},c_{1})\in R_{b_{1}}$
and since $f$ preserves $R_{b_{1}}$ we have that
$(f(a_{1},a_{2}),f(c_{1},c_{2}))=(a_{1},c_{2})\in R_{b_{1}}$, and hence
$(a_{1},b_{1},c_{2})\in R$, which concludes the proof. ∎

Observe that this implies that $\operatorname{\mathfrak{A}^{b}_{0}}$ and
$\operatorname{\mathfrak{A}}$ have exactly the same semilatice edges. The
following example shows that in general it does not hold that
$\operatorname{Pol}(\operatorname{\mathfrak{A}^{b}_{0}})\subseteq\operatorname{Pol}(\operatorname{\mathfrak{A}_{0}})$.

######  Example B.8.

Let $\mathbf{K}$ be the relation algebra with two atoms
$\\{\operatorname{Id},E\\}$ and the multiplication table given in Figure 5. It
is easy to see that the expansion of the infinite clique $K_{\omega}$ by all
first-order definable binary relations is a normal representation of
$\mathbf{K}$. Then $\mathfrak{K}_{0}$ does not have a majority polymorphism,
but $\mathfrak{K}^{b}_{0}$ does since every binary relation on a two-element
set is preserved by the (unique) majority operation on a two-element set.

$~{}\circ~{}$ | $~{}\operatorname{Id}~{}$ | $E$
---|---|---
$\operatorname{Id}$ | $\operatorname{Id}$ | $E$
$E$ | $E$ | $1$
Figure 5: Multiplication table of the relation algebra $\mathbf{K}$.

###  B.3 No Affine Edges in the Atom Structure

We show in this section that under the assumption that
$\operatorname{\mathfrak{A}^{b}_{0}}$ has a Siggers polymorphism and has no
affine edge, $\operatorname{\mathfrak{A}_{0}}$ also has no affine edge. So let
us assume for the whole section that
$\operatorname{Pol}(\operatorname{\mathfrak{A}^{b}_{0}})$ contains a Siggers
operation and that $\operatorname{\mathfrak{A}^{b}_{0}}$ has no affine edge.

Since $\operatorname{\mathfrak{A}^{b}_{0}}$ is conservative and has no affine
edge, there exists according to Proposition A.1 a binary operation
$v\in\operatorname{Pol}(\operatorname{\mathfrak{A}_{0}})$ and a ternary
operation $w\in\operatorname{Pol}(\operatorname{\mathfrak{A}_{0}})$ such that
for every two element subset $C$ of $A_{0}$,

  * •

$v|_{C}$ is a semilattice operation whenever $C$ has a semilattice edge, and
$v|_{C}(x,y)=x$ otherwise;

  * •

$w|_{C}$ is a majority operation if $C$ is a majority edge and
$w|_{C}(x,y,z)=v|_{C}(v|_{C}(x,y),z)$ if $C$ has a semilattice edge.

We define

$u(x,y,z):=w(v(v(x,y),z),v(v(y,z),x),v(v(z,x),y)).$

######  Lemma B.9.

The structures $\operatorname{\mathfrak{A}_{0}}$ and
$\operatorname{\mathfrak{A}^{b}_{0}}$ have exactly the same semilattice edges.
Let $a,b\in A_{0}$ be such that $\\{a,b\\}$ has no semilattice edge in the two
structures. Then the restriction of $u$ to $\\{a,b\\}$ is a majority
operation.

###### Proof.

By Lemma B.6 and Lemma B.7, the structures $\operatorname{\mathfrak{A}_{0}}$
and $\operatorname{\mathfrak{A}^{b}_{0}}$ have exactly the same semilattice
edges, since they have the same binary polymorphisms. The second statement
follows from the definition of $u$ by means of $w$ and $v$. ∎

######  Definition B.10.

Let $f$ be a binary operation on $A_{0}$. Then we say that
$\\{a,b,c\\}\subseteq A_{0}$ has the _$f$ -cycle $(x,y,z)$_ if
$\\{x,y,z\\}=\\{a,b,c\\}$ and $(x,y)$, $(y,z)$, and $(z,x)$ are $f$-sl.

######  Lemma B.11.

Let $a,b,c\in A_{0}$ be such that $(a,b)$ is $v$-sl but $(a,b,c)$ is not a
$v$-cycle. Then $u(r,s,t)\not=a$ for any choice of $r,s,t\in A_{0}$ such that
$\\{r,s,t\\}=\\{a,b,c\\}$.

###### Proof.

We prove a series of intermediate claims.

Claim 1: If $\\{x,y,z\\}=\\{a,b,c\\}$ and $v(v(x,y),z)=a$, then $z=a$. We
assume for contradiction that $z\neq a$ and distinguish the following cases.

  1. 1.

$x=a,y=b,z=c$: Then $v(v(x,y),z)=v(b,c)\in\\{b,c\\}$.

  2. 2.

$x=a,y=c,z=b$: Then $v(v(x,y),z)\in\\{v(a,b),v(c,b)\\}\subseteq\\{b,c\\}$.

  3. 3.

$x=b,y=a,z=c$: Then $v(v(x,y),z)=v(b,c)\in\\{b,c\\}$.

  4. 4.

$x=c,y=a,z=b$: Then $v(v(x,y),z)\in\\{v(c,b),v(a,b)\\}\subseteq\\{b,c\\}$.

In all four cases we have $v(v(x,y),z)\neq a$, which contradicts our
assumption and proves the claim.

Claim 2: If $\\{x,y,z\\}=\\{a,b,c\\}$ and $v(v(x,y),z)=a$, then $(c,a)$ is
$v$-sl.

By Claim 1 we get that $z=a$ and furthermore we have $v(x,y)=v(b,c)=c$ since
otherwise $v(x,y)=v(b,c)=b$ and $v(v(x,y),z)=v(b,a)=b$, which contradicts our
assumption. Assume for contradiction that $(c,a)$ is not $v$-sl and therefore
one of the following holds:

  1. 1.

$(a,c)$ is $v$-sl. It follows that $v(v(x,y),z)=v(c,a)=c$ which contradicts
our assumption.

  2. 2.

$\\{a,c\\}$ is a majority edge of $\operatorname{\mathfrak{A}^{b}_{0}}$. It
follows again that $v(v(x,y),z)=v(c,a)=c$, since $v$ behaves like the
projection on the first coordinate on majority edges. This contradicts our
assumption.

Claim 3: If $\\{x,y,z\\}=\\{a,b,c\\}$ and $v(v(x,y),z)=a$, then $\\{b,c\\}$ is
a majority edge of $\operatorname{\mathfrak{A}^{b}_{0}}$.

Assume for contradiction that there is a semilattice edge on
$\\{b,c\\}=\\{x,y\\}$. By Claim 2 and our assumption that $(a,b,c)$ is not a
$v$-cycle, the edge $(b,c)$ is not $v$-sl and therefore $(c,b)$ is $v$-sl.
Therefore, we get $v(v(x,y),z)=v(b,a)=b$ which contradicts our assumption.

Claim 4: If $\\{x,y,z\\}=\\{a,b,c\\}$ and $v(v(x,y),z)=a$, then
$v(v(z,x),y)=b=v(v(y,z),x)$ follows. By Claim 3, $\\{b,c\\}$ is a majority
edge of $\operatorname{\mathfrak{A}^{b}_{0}}$ and it follows that $b=y$ and
$c=x$ since otherwise $v(v(x,y),z)=v(b,a)=b$. Now we calculate

$v(v(z,x),y))=v(v(a,c),b))=v(a,b)=b=v(b,c)=v(v(b,a),c)=v(v(y,z),x)$

which proves the claim.

Now we are able to prove the statement of the lemma. Assume for contradiction
that $u(r,s,t)=a$. Since $w$ preserves $U_{A\setminus\\{a\\}}$ this is only
possible if at least one of the terms $v(v(r,s),t)$, $v(v(s,t),r)$, or
$v(v(t,r),s))$ evaluates to $a$. By Claim 4 we get that the two other terms
evaluate to $b$. Since $(a,b)$ is $v$-sl we get that
$w(a,b,b)=w(b,a,b)=w(b,b,a)=b$ which contradicts our assumption $u(r,s,t)=a$.
∎

######  Theorem B.12.

If $u\in\operatorname{Pol}(\mathfrak{A}_{0}^{b})$, then
$u\in\operatorname{Pol}(\mathfrak{A}_{0})$.

###### Proof.

We have to prove that $u$ preserves $R$. Let
$(a_{1},b_{1},c_{1}),(a_{2},b_{2},c_{2}),(a_{3},b_{3},c_{3})\in R$ and let

$(a,b,c):=(u(a_{1},a_{2},a_{3}),u(b_{1},b_{2},b_{3}),u(c_{1},c_{2},c_{3})).$

Assume for contradiction that $(a,b,c)\not\in R$. By Lemma B.2, we may assume
without loss of generality that $(a,a,b)\not\in R$ and hence by Lemma B.3
$(a,b)$ is a semilattice edge in $\operatorname{\mathfrak{A}_{0}}$ and $(b,a)$
is not. By Lemma B.9 the structures $\operatorname{\mathfrak{A}_{0}}$ and
$\operatorname{\mathfrak{A}^{b}_{0}}$ have exactly the same semilattice edges.
This implies that $\\{a,b\\}$ has a semilattice edge; this semilattice edge
can only be $(a,b)$ and therefore $(a,b)$ is $v$-sl. Since $u$ preserves
$R_{a_{1}}\cup R_{a_{2}}\cup R_{a_{3}}$ there exists
$r\in\\{a_{1},a_{2},a_{3}\\}$ such that $(r,b,c)\in R$. By Lemma B.4 we get
that $(r,a)$ is not a semilattice edge in $\mathfrak{A}_{0}$ and therefore
Lemma B.7 implies that $(r,a)$ is not a semilattice edge in
$\operatorname{\mathfrak{A}^{b}_{0}}$ and we get that $(r,a)$ is not $v$-sl.
Let $s\in\\{a_{1},a_{2},a_{3}\\}\setminus\\{a,r\\}$.

Claim 1: $\\{a,r,s\\}$ does not have a $v$-cycle. Assume for contradiction
that $\\{a,r,s\\}$ has a $v$-cycle. Since $(r,a)$ is not $v$-sl it follows
that $(a,r)$ is $v$-sl and therefore $(s,a)$ is $v$-sl. We consider the
following two cases:

  1. 1.

$(s,b,c)\in R$. Then Lemma B.4 applied to $a,s,b,c$ implies that $(s,a)$ is
not a semilattice edge and therefore by Lemma B.7 $(s,a)$ is not $v$-sl, which
is a contradiction.

  2. 2.

$(s,b,c)\not\in R$. Note that $(s,s,b)\not\in R$ holds, since $(s,a)$ is
$v$-sl and $v((s,s,b),(a,a,a))=(a,a,b)\in R$ yields a contradiction to
$(a,a,b)\not\in R$. Hence, Lemma B.4 applied to $s,r,b,c$ implies that $(r,s)$
is not a semilattice edge and therefore by Lemma B.7 $(r,s)$ is not $v$-sl,
which is again a contradiction.

This proves that $\\{a,r,s\\}$ cannot have a $v$-cycle.

Claim 2: $u(a,a,r)=a$. Assume for contradiction that $u(a,a,r)=r$. Then
$\\{a,r\\}$ is clearly not a majority edge of
$\operatorname{\mathfrak{A}^{b}_{0}}$, and since
$\operatorname{\mathfrak{A}^{b}_{0}}$ does not have affine edges it follows
that $(a,r)$ is $v$-sl. Furthermore, $(a,r,s)$ is not a $v$-cycle and
therefore Lemma B.11 implies that $u(a_{1},a_{2},a_{3})\not=a$ which
contradicts the definition of $a$.

Finally, consider the following application of the polymorphism $u$:

$u\big{(}(a,a),(a,a),(r,b)\big{)}=(a,b).$

Since $(a,a)\in R_{a}$ and $(r,b)\in R_{c}$ and since $u$ is in
$\operatorname{Pol}(\mathfrak{A}_{0}^{b})$ we get that $(a,b)\in R_{a}\cup
R_{c}$. Hence, ${(a,a,b)}\in R$ or $(c,a,b)\in R$, which contradicts our
assumptions. ∎

###  B.4 Proof of the Main Theorem

We can now prove the main result of this section.

###### Proof of Theorem 4.4..

Let $\operatorname{\mathbf{A}}$ be a finite relation algebra that satisfies
the assumptions of Theorem 4.4 and let $\operatorname{\mathfrak{A}_{0}}$ be
the atom structure of $\operatorname{\mathbf{A}}$ (Definition 2.15). We denote
by $\operatorname{\mathfrak{A}^{b}_{0}}$ the binarisation of
$\operatorname{\mathfrak{A}_{0}}$ according to Definition B.5. It follows from
the assumptions on $\operatorname{\mathbf{A}}$ that
$\operatorname{Pol}(\operatorname{\mathfrak{A}_{0}})$ contains a Siggers
operation. By Lemma B.6 we get that
$\operatorname{Pol}(\operatorname{\mathfrak{A}^{b}_{0}})$ contains a Siggers
operation as well. Note that $\operatorname{\mathfrak{A}^{b}_{0}}$ is a finite
binary conservative structure and therefore Theorem 4.6 implies that
$\operatorname{\mathfrak{A}^{b}_{0}}$ has no affine edges. Therefore,
$\operatorname{\mathfrak{A}^{b}_{0}}$ satisfies the general assumption from
Section B.3 and we can define the operation $u$ as it is done in the beginning
of this section. Note that $u$ witnesses by Lemma B.9 that
$\operatorname{\mathfrak{A}^{b}_{0}}$ does not have an affine edge. We can now
apply Theorem B.12 and get that $u$ is also a polymorphism of
$\operatorname{\mathfrak{A}_{0}}$. Recall that
$\operatorname{\mathfrak{A}_{0}}$ and $\operatorname{\mathfrak{A}^{b}_{0}}$
have by Lemma B.7 exactly the same semilattice edges and therefore Lemma B.9
and the fact that $u$ is a polymorphism of $\operatorname{\mathfrak{A}_{0}}$
imply that $\operatorname{\mathfrak{A}_{0}}$ does not have an affine edge. By
Proposition 4.5 we get that there exists a $3$-ary weak near unanimity
polymorphism $f\in\operatorname{Pol}(\operatorname{\mathfrak{A}_{0}})$ and a
$4$-ary weak near unanimity polymorphism
$g\in\operatorname{Pol}(\operatorname{\mathfrak{A}_{0}})$ such that

$\forall x,y,z\in B.~{}f(y,x,x)=g(y,x,x,x)$

holds. Theorem 2.23 implies that
$\operatorname{CSP}(\operatorname{\mathfrak{B}})$ and thus also
$\operatorname{NSP}(\operatorname{\mathbf{A}})$ can be solved by
$(4,6)$-consistency algorithm. ∎

##  Appendix C The Complexity of the Meta Problem

See 6.2

###### Proof.

By Theorem 5.2 it suffices to test the existence of an operation $f\colon
A^{6}_{0}\to A_{0}$ which satisfies conditions 1.-3. in this theorem. The
three conditions can clearly be checked in polynomial time, so we already know
that $\operatorname{Meta}$ is in NP.

Note that the search for $f$ may be phrased as an instance of
$\operatorname{CSP}(\operatorname{\mathfrak{A}}_{0})$ with $|A|^{6}$
variables. Using the fact that the $k$-consistency procedure is one-sided
correct even in the case that
$\operatorname{CSP}(\operatorname{\mathfrak{A}}_{0})$ is NP-hard (i.e., if the
procedure rejects a given instance of
$\operatorname{CSP}(\operatorname{\mathfrak{A}}_{0})$, then the instance is
always unsatisfiable), we may use a standard self-reducibility argument (see,
e.g., [CL17]) to obtain a polynomial-time algorithm for finding $f$. ∎