The Network Satisfaction Problem for Relation Algebras with at Most 4 Atoms

Bodirsky, Manuel; Jahn, Moritz; Knäuer, Simon; Konečný, Matěj; Winkler, Paul

doi:10.4230/LIPIcs.ICALP.2026.168

The Network Satisfaction Problem for Relation Algebras with at Most 4 Atoms

Manuel Bodirsky

Institut für Algebra, TU Dresden, Germany Moritz Jahn

Institut für Algebra, TU Dresden, Germany Simon Knäuer

Institut für Algebra, TU Dresden, Germany Matěj Konečný

Institut für Algebra, TU Dresden, Germany Paul Winkler

Institut für Algebra, TU Dresden, Germany

Abstract

Andréka and Maddux classified the relation algebras with at most 3 atoms, and in particular they showed that all of them are representable [1]. Hirsch and Cristiani showed that the network satisfaction problem (NSP) for each of these algebras is in $\operatorname{\mathbf{P}}$ or $\operatorname{\mathbf{NP}}$ -hard [26]. The literature contains many results on representations of relation algebras; in particular, some relation algebras with four atoms are not representable. We extend the result of Cristiani and Hirsch to relation algebras with at most 4 atoms: the NSP is always either in $\operatorname{\mathbf{P}}$ or $\operatorname{\mathbf{NP}}$ -hard. To this end, we construct universal, fully universal, or even normal representations for these algebras, whenever possible.

Keywords and phrases:

Constraint Satisfaction, Computational Complexity, Relation Algebras, Network Satisfaction, Normal Representations, Polynomial-Time Algorithms

Category:

Track B: Automata, Logic, Semantics, and Theory of Programming

Copyright and License:

2012 ACM Subject Classification:

Theory of computation ; Theory of computation

\rightarrow

Constraint and logic programming ; Theory of computation

\rightarrow

Problems, reductions and completeness

Related Version:

Full Version: https://arxiv.org/abs/2507.09324

Supplementary Material:

Software (Source Code): https://github.com/paulwinkler1/RelationAlgebrasWith4Atoms
archived at

swh:1:dir:49ad37df7cfccfe236d65a17a248eacb9dfd1557

Funding:

Manuel Bodirsky, Moritz Jahn, Matěj Konečný, and Paul Winkler received funding from the ERC (Grant Agreement no. 101071674, POCOCOP). Views and opinions expressed are however those of the authors only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency.

DOI:

10.4230/LIPIcs.ICALP.2026.168

Event:

53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Editors:

Sayan Bhattacharya, Danupon Nanongkai, Michael Benedikt, and Gabriele Puppis

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Relation algebras are algebraic structures that can be used to abstractly reason about binary relations. They are certain expansions of Boolean algebras; besides the operations for union, intersection, and complement of binary relations, we also have a binary operation $\circ$ for composition of relations, and a unary operation $\breve{\phantom{}}$ for reversing the arguments of a binary relation. These operations need to satisfy certain natural identities; e.g., we require that $(a\circ b)\,\breve{\phantom{}}=\breve{b}\circ\breve{a}$ holds for all elements $a$ and $b$ of the relation algebra.

Similarly to the fundamental facts that every group is isomorphic to a permutation group, and every Boolean algebra is isomorphic to an algebra of sets, the initial hope was that every relation algebra has a representation, which consists of a set of binary relations on some set that behave as prescribed by the relation algebra [39].

Example 1.

We first look at a concrete structure from which a small relation algebra can be obtained. Consider the structure $(\mathbb{Q};<)$ , where ${\mathbb{Q}}$ is the set of rational numbers and $<$ is the usual strict linear order on ${\mathbb{Q}}$ . For any two rational numbers $x, y$ , exactly one of the following holds: $x<y$ , $x=y$ , or $x>y$ . Thus, the relations $<$ , $=$ , and $>$ form a partition of $\mathbb{Q}^{2}$ . Moreover, $\breve{<}={>}$ , where $\breve{\nobreak\ }$ denotes the usual converse operation on binary relations, defined by $\breve{R}=\{(y,x)\mid(x,y)\in R\}$ .

This partition gives rise to a relation algebra $\mathbf{A}$ with three atoms, denoted by $r$ , $\operatorname{Id}$ , and $\breve{r}$ . Its domain $A$ consists of all formal unions of these atoms, i.e., $A=\{0,\allowbreak r,\allowbreak\breve{r},\allowbreak\operatorname{Id},% \allowbreak r\cup\operatorname{Id},\allowbreak\breve{r}\cup\operatorname{Id},% \allowbreak r\cup\breve{r},\allowbreak r\cup\breve{r}\cup\operatorname{Id}\}$ . The other Boolean operations are defined in the usual way.

Let $\circ$ denote the usual composition of binary relations, i.e.,

R\circ S=\{(x,z)\mid\exists y\colon(x,y)\in R\text{ and }(y,z)\in S\}.

In $(\mathbb{Q};<)$ , for example, we have ${<\circ<}={<}$ and ${<\circ>}={(<\cup>\cup=)}$ . Accordingly, $\mathbf{A}$ has a binary operation, also denoted by $\circ$ , satisfying, for example, $r\circ r=r$ and $r\circ\breve{r}=(r\cup\breve{r}\cup\operatorname{Id})$ .

Note that $\mathbf{A}$ is a Boolean algebra with $8$ elements, together with a binary operation $\circ$ and a unary operation $\breve{\nobreak\ }$ . Instead of obtaining $\mathbf{A}$ from concrete relations on $\mathbb{Q}$ , one may also start with the abstract algebra $\mathbf{A}$ and ask whether it has a “representation”, similarly as above. Formally, we ask whether there exists a set $D$ and an injective homomorphism $h\colon A\to\mathcal{P}(D^{2})$ preserving the Boolean operations, converse, and composition. In particular, distinct atoms are mapped to disjoint binary relations, while formal unions such as $r\cup\operatorname{Id}$ are mapped to the corresponding unions. In the present example, the ordered set $(\mathbb{Q};<)$ provides such a representation: take $D=\mathbb{Q}$ and map $r$ , $\operatorname{Id}$ , and $\breve{r}$ to the relations $<$ , $=$ , and $>$ , respectively. The value of $h$ on all other elements of $A$ is then determined by preservation of the Boolean operations; for example, $h(r\cup\operatorname{Id})=h(r)\cup h(\operatorname{Id})=({<}\cup{=})$ . $\triangle$

1.1 Network Satisfaction Problems and CSP Complexity

Starting in the 90s, another generation of researchers investigated relation algebras motivated by applications in theoretical computer science, particularly for the theory of constraint satisfaction. In a constraint satisfaction problem, we are given a finite set of variables and a finite set of constraints, and the task is to determine whether there exists an assignment to the variables that satisfies all the constraints. Constraint satisfaction problems have been studied intensively if the variables take values from a fixed finite domain. Relation algebras allow one to formalize interesting constraint satisfaction problems where the variables may take values from an infinite domain.

Concretely, to every finite relation algebra $\mathbf{A}$ , we may associate the so-called network satisfaction problem, which is a computational problem where the input consists of a “constraint network”, i.e., a finite set of nodes $V$ and a function labeling pairs of nodes with elements from the relation algebra, and the task is to decide whether there exists a representation of $\mathbf{A}$ where this network is satisfiable. Under certain representability conditions, e.g., if $\mathbf{A}$ has a square representation ([7, Section 1.5]; definitions may be found in Section 2), the network satisfaction problem for $\mathbf{A}$ is a constraint satisfaction problem as described above, but not necessarily for values from a finite set (the values rather come from the elements of the representation, which might be infinite).

If there is a so-called fully universal representation, then the network satisfaction problem is in $\operatorname{\mathbf{NP}}$ . However, the complexity sometimes even drops to $\operatorname{\mathbf{P}}$ (polynomial time). The computational complexity of the NSP has been shown to be $\operatorname{\mathbf{NPc}}$ ( $\operatorname{\mathbf{NP}}$ -complete) or $\operatorname{\mathbf{P}}$ for each relation algebra with at most $8=2^{3}$ elements by Cristiani and Hirsch [26] (such relation algebras are called “small relation algebras”).

Example 2.

Let $\mathbf{A}$ be the relation algebra from Example 1. An $\mathbf{A}$ -network consists of finitely many nodes and a function $f\colon V^{2}\rightarrow A$ mapping each ordered pair to some element of the relation algebra. Under the representation over $(\mathbb{Q};<)$ , the label $f(x,y)$ specifies the allowed relative position of the values assigned to $x$ and $y$ .

For instance, consider a network with nodes $x, y, z$ and function $f$ such that $f(x,y)=r$ , $f(y,z)=r\cup\operatorname{Id}$ , and $f(z,x)=\breve{r}\cup\operatorname{Id}$ , and such that all other pairs are labeled by ${r\cup\breve{r}\cup\operatorname{Id}}$ . Under the representation over $(\mathbb{Q};<)$ , these constraints mean $x<y$ , $y\leq z$ , and $z\geq x$ , respectively. This network is satisfiable, for example by assigning $x=0$ , $y=1$ , and $z=2$ .

On the other hand, if $f(x,y)=r$ , $f(y,z)=r$ , and $f(z,x)=r$ , then the network is not satisfiable in this representation, since it would require $x<y<z<x$ .

In fact, the representation over $(\mathbb{Q};<)$ is normal, in particular fully universal; see Section 2 for the definitions. The fact that the representation is fully universal implies that the network satisfaction problem for $\mathbf{A}$ amounts to deciding whether a finite system of constraints over the signature $\{\varnothing,<,\leq,>,\geq,=,\neq,\mathbb{Q}^{2}\}$ can be satisfied over the rational numbers. $\triangle$

Hirsch [30] asked whether the computational complexity of the network satisfaction problem can be classified for all finite relation algebras. Bodirsky and Knäuer [12] proved that the problem of deciding whether a given finite relation algebra has an NSP which is in $\operatorname{\mathbf{P}}$ is undecidable, which can be interpreted as a negative answer to Hirsch’s question. The proof of the undecidability result relies on two earlier results, namely that there are finite relation algebras whose NSP is undecidable [31], and that the question whether a finite relation algebra has a representation is undecidable [29]. The classification for relation algebras with a fully universal representation, however, remains wide open.

A particularly interesting subclass are the relation algebras that have a normal representation, i.e., a representation which is fully universal, square, and homogeneous [30]. While this combination of assumptions still captures a rich class of relation algebras, it has a wide range of strong and useful consequences, as we will see below. A relational structure is homogeneous if every isomorphism between finite substructures can be extended to an automorphism of the structure. If a relation algebra $\mathbf{A}$ has a normal representation, then $\mathbf{A}$ has a countable normal representation $\mathfrak{B}$ , and this representation is unique up to isomorphism. Moreover, one can express important properties of the automorphism group of $\mathfrak{B}$ using $\mathbf{A}$ , and conversely, properties of $\mathbf{A}$ are reflected in this group. It is known that the question whether a given finite relation algebra has a normal representation is decidable [6].

The NSPs for relation algebras with a normal representation fall into the scope of the so-called tractability conjecture in constraint satisfaction, which implies that CSPs of reducts of finitely bounded homogeneous structures are in $\operatorname{\mathbf{P}}$ or $\operatorname{\mathbf{NP}}$ -complete [16]. In particular, the subclasses of $\operatorname{\mathbf{NP}}$ that properly lie between $\operatorname{\mathbf{P}}$ and $\operatorname{\mathbf{NP}}$ and were constructed by Ladner [34] (conditionally on $\operatorname{\mathbf{P}}\neq\operatorname{\mathbf{NP}}$ ) do not show up when classifying such NSPs. Such a dichotomy statement has been established for CSPs of finite structures [42] (announced independently by Bulatov [18] and by Zhuk [43]). One of the motivations for the more general conjecture from [16] is that many of the universal-algebraic methods used by both Bulatov and Zhuk can be applied for the more general class. And indeed, there exists a universal-algebraic condition which is a candidate for separating polynomial-time tractable from $\operatorname{\mathbf{NP}}$ -complete CSPs for reducts of finitely bounded homogeneous structures, and this condition has numerous equivalent characterisations [16, 4, 3, 5, 7]. If this condition applies, the CSP is provably $\operatorname{\mathbf{NP}}$ -hard; if not, then the conjecture states that the CSP is in $\operatorname{\mathbf{P}}$ . In our case, the tractability conjecture can be formulated as follows (for the definition of pp-constructability, see Section 2). Let $\operatorname{NAE}:=\{0,1\}^{3}\setminus\{(0,0,0),(1,1,1)\}$ be the ternary Boolean not-all-equal relation.

Conjecture 2.

Let $\mathfrak{B}$ be a normal representation of a finite relation algebra $\mathbf{A}$ . If $\mathfrak{B}$ does not pp-construct $(\{0,1\};\operatorname{NAE})$ , then $\operatorname{CSP}(\mathfrak{B})$ and $\operatorname{NSP}(\mathbf{A})$ are in $\operatorname{\mathbf{P}}$ .¹¹1In the case where $\mathfrak{B}$ is a normal representation of $\mathbf{A}$ , $\operatorname{CSP}(\mathfrak{B})$ and $\operatorname{NSP}(\mathbf{A})$ are the same computational problem up to the translation between $\mathbf{A}$ -networks and $A$ -structures.

We mention that the scope of the tractability conjecture from [16] for NSPs of relation algebras is larger than just the relation algebras with a normal representation: e.g., if a relation algebra has a representation which is homogenizable in the sense that we can add finitely many first-order definable relations to make it homogeneous, then its NSP is covered as well.

Homogeneous structures are also of central interest in model theory; via Fraïssé’s theorem, they are particularly easy to construct and provide a rich source of examples and counterexamples. It is conceivable that the class of homogeneous structures with a finite relational signature can be classified in some sense. There are uncountably many [28], but the uncountable families usually have a particularly simple shape [23]. One of the approaches in the study of homogeneous structures is to fix some (often binary) relational signature (e.g., the signature of graphs [33], digraphs [23], permutations [21], metric spaces [22], etc.) and to then classify the homogeneous structures with this signature. One of the motivations for this research program is its success story of producing beautiful and interesting mathematical structures that have inspired research in the areas mentioned above. Systematically listing finite relation algebras and then testing for the existence of a normal representation is another approach that can produce interesting new examples of homogeneous (or homogeneizable) structures.

There are potentially further well-behaved subclasses of representable relation algebras beyond those admitting homogenizable or even normal representations. To identify such classes, it is natural to consider families of relation algebras that are both sufficiently representative and sufficiently small to allow for a detailed analysis. Restricting the number of atoms provides such a family.

1.2 Contributions

We extend the mentioned result of Hirsch and Cristiani on small relation algebras, and systematically study all relation algebras with at most $16=2^{4}$ elements. An exhaustive list of the building blocks for such relation algebras has been computed by Maddux [37], confirming results of Comer [25], namely a list for the integral symmetric relation algebras with four atoms (numbered ${1_{65}}$ – ${65_{65}}$ by Maddux) and a list for the integral relation algebras with an asymmetric atom among its four atoms (numbered ${1_{37}}$ – ${37_{37}}$ by Maddux).

We prove that the NSPs for these not so small relation algebras are in $\operatorname{\mathbf{P}}$ or $\operatorname{\mathbf{NP}}$ -hard. In the case where the algebra has a normal representation, our results confirm the mentioned tractability conjecture from [16]. More formally, we obtain the following results.

Theorem 3.

Let $\mathbf{A}$ be a finite relation algebra with at most four atoms. Then $\operatorname{NSP}(\mathbf{A})$ is in $\operatorname{\mathbf{P}}$ or $\operatorname{\mathbf{NP}}$ -hard.

Theorem 4.

Let $\mathfrak{B}$ be a normal representation of a finite relation algebra $\mathbf{A}$ with at most four atoms. If $\mathfrak{B}$ does not pp-construct $(\{0,1\};\operatorname{NAE})$ , then $\operatorname{CSP}(\mathfrak{B})$ and $\operatorname{NSP}(\mathbf{A})$ are in $\operatorname{\mathbf{P}}$ .

For all but one of these algebras we also prove the containment of the NSP in $\operatorname{\mathbf{NP}}$ ; the one exceptional case is ${56_{65}}$ . Actually, its NSP is also contained in $\operatorname{\mathbf{NP}}$ , but the proof requires substantially different techniques and is published separately (see [8]).

In addition to our classification of NSP complexity, we revisit representability for all finite relation algebras with at most 4 atoms. Several of the algebras in the list do not have a representation (in which case the NSP is trivial and in $\operatorname{\mathbf{P}}$ ). We determine for each of the representable algebras $\mathbf{A}$ whether $\mathbf{A}$ has a normal representation, and if not, whether at least it has a fully universal (or even fully universal square) representation. This result is of independent interest in the theory of relation algebras; representations for all relation algebras with at most 3 atoms have been found in 1994 [1]. For this purpose, we present a combinatorial characterization for the existence of a fully universal square representation.

We think of this paper as exploratory work towards more general classifications of the complexity of NSPs, or representability questions, of suitable subclasses of relation algebras. Maddux’s list of relation algebras with at most four atoms is at the same time rich enough to display diverse behaviour, while remaining small enough for detailed analysis, including computer-assisted inspection.

We verified that in many cases, the existing methods apply (e.g. [12, 11, 10]). At the same time, we also needed to develop new methods (such as proving $\operatorname{\mathbf{NP}}$ -hardness of the NSPs by reductions from the approximate graph coloring problem $\operatorname{CSP}(K_{3},K_{5})$ [19]; a so-called promise constraint satisfaction problem), as well as several ad hoc arguments for concrete cases. Several of these deserve explicit mention.

$\blacksquare$

${24_{65}}$ ; this algebra is related to the class of 3-edge-coloured cliques with no rainbow triangle, which exhibits some nice combinatorics, and has a fully universal representation. Our structural insights are then the basis for a polynomial-time algorithm for its NSP; see Section 5.1 for details.
$\blacksquare$

${17_{37}}$ ; this algebra is related to the class of quasi-transitive oriented graphs, which has been studied in graph theory [2]. There is no fully universal representation and we identify an atomic network with 4 vertices which is consistent but unsatisfiable. By working with the class of consistent atomic networks that exclude this 4-element network, we can construct a universal representation for ${17_{37}}$ . Our structural insights in combination with results from [2] are then also useful for a polynomial-time algorithm for the NSP of ${17_{37}}$ .
$\blacksquare$

${51_{65}}$ ; this algebra contains exactly one non-trivial equivalence relation, and in every representation, the equivalence relation can have at most 3 classes. Our representability results for this algebra follow a similar pattern as our results for ${17_{37}}$ : while there is no fully universal representation, we can identify four atomic networks that are consistent but unsatisfiable. Excluding those, we can construct a universal representation; it follows that the NSP is in $\operatorname{\mathbf{NP}}$ , and in fact it is $\operatorname{\mathbf{NP}}$ -complete.
$\blacksquare$

${56_{65}}$ ; this relation algebra is similar to the previous one, but allows one extra triple compared to ${51_{65}}$ . It has a representation, but not a fully universal one. Its NSP is $\operatorname{\mathbf{NP}}$ -hard.

There are already several thousand relation algebras with five atoms [37], making a direct extension of the present classification substantially more challenging. The four-atom examples are expected to correspond to large subclasses of the five-atom list, and analysing these subclasses will help to identify useful generalisations by methods developed in this article.

1.3 Significance for Constraint Satisfaction

We believe that network satisfaction problems for relation algebras with a normal representation are an important class on which to test the mentioned tractability conjecture. The reason is that this approach can lead to CSPs with different behaviour, challenging the current methods. Previously, the tractability conjecture has mainly been tested on structures obtained as follows: fix a homogeneous finitely bounded “base” structure of fundamental interest (such as $({\mathbb{Q}};<)$ or the Rado graph), and study the CSP of all first-order reducts of it (see, e.g., [9, 15]). The advantage of this approach is that the model-theoretic properties of the entire class of structures obtained like this are inherited from the base structure, and the remaining task is mostly universal-algebraic. This advantage is at the same time a disadvantage, because by fixing a base structure we might overlook some phenomena that only appear for other base structures. The approach of the present article avoids this; and indeed, our study shows that new structures with different behaviour and interesting polynomial-time CSPs may show up.

2 Preliminaries

In the following, we will introduce some concepts from universal algebra and constraint satisfaction, as well as formal definitions of relation algebras and representations.

2.1 Constraint Satisfaction

Our basic terminology and notation (relational structures, homomorphisms, etc.) is standard; see e.g., [32], or the long version of the article. Let $\mathfrak{B}$ be a structure with a finite relational signature $\tau$ . Then the constraint satisfaction problem $\operatorname{CSP}(\mathfrak{B})$ is the problem of deciding for a given finite $\tau$ -structure $\mathfrak{A}$ whether there exists a homomorphism to $\mathfrak{B}$ .

Example 5.

$\operatorname{CSP}(\{0,1\};\operatorname{NAE})$ is the positive not-all-equal 3-SAT problem, which is $\operatorname{\mathbf{NP}}$ -complete [27]. $\triangle$

A more refined tool than many-one reductions to determine the computational complexity of a CSP are pp-interpretations and pp-constructions. The advantage of these kinds of reductions is that they have an algebraic characterization and hence open up ways of solving complexity questions by means of universal algebra. A formula is called primitive positive (shortly pp) if it is of the form $\exists x_{1}\cdots\exists x_{k}(\psi_{1}\land\cdots\land\psi_{n})$ , where each $\psi_{i}$ is atomic, i.e., of the form $\top$ , $\bot$ , $x=y$ , or $R(x_{i1},\ldots,x_{il})$ for some relation $R$ in the signature.

Definition 6.

Let $\mathfrak{A}$ and $\mathfrak{B}$ be structures with relational signatures $\tau$ and $\sigma$ , respectively. A primitive positive interpretation of dimension $d$ of $\mathfrak{A}$ in $\mathfrak{B}$ is a partial surjection $h\colon\mathrm{dom}(h)\subseteq B^{d}\rightarrow A$ such that for every relation $R$ , say of arity $k$ , which can be defined by an atomic formula over $\mathfrak{A}$ , the $(k\cdot d)$ -ary relation $h^{-1}(R)$ given by

\displaystyle\{(b_{11},\ldots,b_{1d},\ldots,b_{k1},\ldots,b_{kd})\in B^{k\cdot d% }\mid(h(b_{11},\ldots,b_{1d}),\ldots,h(b_{k1},\ldots,b_{kd}))\in R^{\mathfrak{% A}}\}

can be defined in $\mathfrak{B}$ by a primitive positive formula $\varphi_{R}$ . Since equality and $\top$ are always allowed as atomic formulas, there must in particular exist

$\blacksquare$

a $\sigma$ -formula $\varphi_{\top}$ (called the domain formula) such that $\varphi_{\top}(b_{1},\ldots,b_{d})$ holds if and only if $(b_{1},\ldots,b_{d})$ is in the domain of $h$ ;
$\blacksquare$

a $\sigma$ -formula $\varphi_{=}$ such that $\varphi_{=}(b_{1},\ldots,b_{d},c_{1},\ldots,c_{d})$ holds if and only if $h(b_{1},\ldots,b_{d})=h(c_{1},\ldots,c_{d})$ .

In this case we say that $\mathfrak{B}$ pp-interprets $\mathfrak{A}$ . We say that $\mathfrak{B}$ pp-constructs $\mathfrak{A}$ if $\mathfrak{B}$ pp-interprets a structure $\mathfrak{C}$ that is homomorphically equivalent to $\mathfrak{A}$ , i.e., there exists a homomorphism from $\mathfrak{A}$ to $\mathfrak{C}$ and one from $\mathfrak{C}$ to $\mathfrak{A}$ .

The following is well-known.

Proposition 7 (see, e.g., [7, Theorem 3.1.4]).

If $\mathfrak{B}$ pp-constructs $\mathfrak{A}$ , then $\operatorname{CSP}(\mathfrak{A})$ is log-space reducible to $\operatorname{CSP}(\mathfrak{B})$ . In particular, if $\mathfrak{B}$ pp-constructs $(\{0,1\};\operatorname{NAE})$ , then $\operatorname{CSP}(\mathfrak{B})$ is $\operatorname{\mathbf{NP}}$ -hard.

An important concept from universal algebra to study the complexity of CSPs of finite and $\omega$ -categorical structures is that of polymorphisms.

Definition 8.

Let $\tau$ be a relational signature. A polymorphism of a $\tau$ -structure $\mathfrak{B}$ is a homomorphism $f$ from the direct product $\mathfrak{B}^{k}$ to $\mathfrak{B}$ .

Intuitively, polymorphisms are a generalisation of automorphisms; the existence of certain polymorphisms of $\mathfrak{B}$ can imply tractability of CSP( $\mathfrak{B}$ ), while non-existence of certain polymorphisms often implies hardness.

2.2 Relation Algebras

(Integral) relation algebras have also been discovered and studied with a different formalism and under the different name of hypergroups [44] (also called polygroups [25]).

Definition 9.

A relation algebra is an algebra $\mathbf{A}$ with domain $A$ and signature $\{\cup,\bar{\phantom{o}},\allowbreak 0,1,\operatorname{Id},\breve{\phantom{o}}% ,\circ\}$ such that

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.

$\circ$ is an associative binary operation on A, called composition;
3.

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

for all $a\in A$ : $a\circ\operatorname{Id}=a$ ;
5.

for all $a\in A$ : $\breve{\breve{a}}=a$ ;
6.

for all $a,b\in A$ : $(a\cup b){\breve{\phantom{o}}}=\breve{a}\cup\breve{b}$ ;
7.

for all $a,b\in A$ : $(a\circ b){\breve{\phantom{o}}}=\breve{b}\circ\breve{a}$ ;
8.

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

If $\mathbf{A}$ is a relation algebra with elements $a$ and $b$ , then we write $a\leq b$ if $a\cap b=a$ holds in $\mathbf{A}$ . Clearly, $\leq$ defines a partial order on $A$ . An element $b\in A\setminus\{0^{\mathbf{A}}\}$ is called an atom if there is no element $a\in A\setminus\{0^{\mathbf{A}},b\}$ with $a\leq b$ . The set of all atoms is denoted by $A_{0}$ .

For a finite relation algebra $\mathbf{A}$ , the operation $\circ$ is completely determined by its restriction to the atoms. A tuple $(x,y,z)\in(A_{0})^{3}$ is called an allowed triple if $z\leq x\circ y$ . Otherwise, $(x,y,z)$ is called a forbidden triple. We denote by

\operatorname{Cy}(\mathbf{A}):=\{(x,y,z)\in A_{0}\mid z\leq x\circ y\}

the set of all allowed triples. An element $a\in A$ is called reflexive if $\operatorname{Id}\leq a$ , symmetric if $\breve{a}=a$ , transitive if $a^{2}\leq a$ , and an equivalence relation if $a$ is reflexive, symmetric, and transitive. A relation algebra $\mathbf{A}$ is called symmetric if all $a\in A$ are symmetric, integral if $0\neq 1$ and $x\circ y=0$ implies $x=0$ or $y=0$ (see [36]), and simple if $1\circ x\circ 1=1$ for all $x\neq 0$ . Each relation algebra has an associated finite relational structure, its atom structure.

Definition 10.

Let $\mathbf{A}$ be a relation algebra. The atom structure of $\mathbf{A}$ is the finite relational structure $\mathfrak{A}_{0}$ with domain $A_{0}$ and the following relations:

$\blacksquare$

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

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

the ternary relation $R^{\mathfrak{A}_{0}}:=\operatorname{Cy}(\mathbf{A})$ .

If $R_{1},R_{2}\subseteq B^{2}$ are two binary relations, then $R_{1}\circ R_{2}$ denotes the composition

\displaystyle R_{1}\circ R_{2}:=\{(x,z)\in B^{2}\mid\text{ there exists }y\in B% \text{ with }(x,y)\in R_{1}\text{ and }(y,z)\in R_{2}\}.

Definition 11.

Let $\mathbf{A}=(A;\cup,\bar{\phantom{o}},0,1,\operatorname{Id},\breve{\phantom{o}}% ,\circ)$ be a relation algebra. A structure $\mathfrak{B}$ with signature $A$ is called a representation of $\mathbf{A}$ if

1.

$0^{\mathfrak{B}}=\varnothing$ ;
2.

$1^{\mathfrak{B}}=\bigcup_{a\in A}a^{\mathfrak{B}}$ ;
3.

$\operatorname{Id}^{\mathfrak{B}}=\{(u,u)\mid u\in B\}$ ;
4.

for all $a\in A$ we have $({\overline{a}})^{\mathfrak{B}}=1^{\mathfrak{B}}\setminus a^{\mathfrak{B}}$ ;
5.

for all $a\in A$ we have $(\breve{a})^{\mathfrak{B}}=\{(u,v)\mid(v,u)\in a^{\mathfrak{B}}\}$ ;
6.

for all $a,b\in A$ we have $a^{\mathfrak{B}}\cup b^{\mathfrak{B}}=(a\cup b)^{\mathfrak{B}}$ ;
7.

for all $a,b\in A$ we have $a^{\mathfrak{B}}\circ b^{\mathfrak{B}}=(a\circ b)^{\mathfrak{B}}$ .

Relation algebras that have a representation are called representable.

All relation algebras with at most $2^{3}=8$ elements have a representation [1]. Tarski [39] asked whether every relation algebra is representable. This question was answered by Lyndon [35], who found a relation algebra with $2^{56}$ elements which is not representable. Monk [38] later showed that this problem has no easy fix, because the class of representable relation algebras cannot be axiomatized by a finite set of identities, and not even by a finite set of first-order sentences, answering another question of Tarski. However, it follows from results of Tarski [40] that there is an infinite set of identities that axiomatizes the representable relation algebras.

A useful tool to construct more complex relation algebras from simpler ones is the so-called 2-cycle product; the construction preserves representability (and, as we will see, even fully universal representability, normal representability, etc.) and it will also be useful in complexity considerations.

Definition 12.

Let $\mathbf{A}$ and $\mathbf{B}$ be two finite relation algebras such that $A_{0}\cap B_{0}=\{\operatorname{Id}\}$ . The 2-cycle product $\mathbf{A}[\mathbf{B}]$ is defined to be the up to isomorphism unique relation algebra $\mathbf{C}$ such that $C_{0}=A_{0}\cup B_{0}$ and

\operatorname{Cy}(\mathbf{C})=\operatorname{Cy}(\mathbf{A})\cup\operatorname{% Cy}(\mathbf{B})\cup\big\{(a,b,b)\mid a\in A_{0}\setminus\{\operatorname{Id}\},% b\in B_{0}\setminus\{\operatorname{Id}\}\big\}.

Definition 13.

If $\mathbf{A}$ is a relation algebra, then an $\mathbf{A}$ -network $(V,f)$ consists of a finite set of variables $V$ and a function $f\colon V^{2}\to A$ (see, e.g., [7, Section 1.5.3]). If $\mathfrak{B}$ is a representation of $\mathbf{A}$ , then $(V,f)$ is called satisfiable in $\mathfrak{B}$ if there exists a function $s\colon V\to B$ such that for all $x,y\in V$ we have $(s(x),s(y))\in f(x,y)^{\mathfrak{B}}$ . An $\mathbf{A}$ -network $(V,f)$ is called

$\blacksquare$

atomic if for all $x,y\in V$ we have that $f(x,y)$ is an atom in $\mathbf{A}$ ;
$\blacksquare$

consistent (also: path-consistent, 3-consistent, or closed) if for all $x,y,z\in V$ we have

$\displaystyle f(x,y)\leq f(x,z)\circ f(z,y)\text{ and }f(x,x)\leq\operatorname% {Id};$ (2.1)
$\blacksquare$

satisfiable if it is satisfiable in some representation of $\mathbf{A}$ .

Definition 14.

The network satisfaction problem for a fixed finite relation algebra $\mathbf{A}$ , denoted by $\operatorname{NSP}(\mathbf{A})$ , is the following computational problem: The input consists of an $\mathbf{A}$ -network $(V,f)$ . The task is to decide whether $(V,f)$ is satisfiable.

Definition 15.

A representation $\mathfrak{B}$ of a relation algebra $\mathbf{A}$ is called universal if every satisfiable $\mathbf{A}$ -network is satisfiable in $\mathfrak{B}$ , and fully universal if every consistent atomic $\mathbf{A}$ -network is satisfiable in $\mathfrak{B}$ .

Definition 16.

A representation $\mathfrak{B}$ of $\mathbf{A}$ is called normal if it is square, fully universal, and homogeneous.

It follows from Theorem 18 below that the question whether a given finite relation algebra has a normal representation is decidable. The following definition is standard in model theory when phrased for structures; we present here a relation algebra version.

Definition 17 (The Amalgamation Property).

Let $\mathbf{A}$ be a relation algebra and let $\mathcal{C}$ be a class of consistent atomic $\mathbf{A}$ -networks. We say that $\mathcal{C}$ has $\operatorname{AP}(k,l,m)$ (the $(k,l,m)$ -amalgamation property) if for any two networks $(V_{1},f_{1}),(V_{2},f_{2})\in{\mathcal{C}}$ with $|V_{1}|=k,|V_{1}\cap V_{2}|=l$ , and $|V_{2}|=m$ , if $f_{1}(a,b)=f_{2}(a,b)$ for all $a,b\in V_{1}\cap V_{2}$ , then there exists a network $(V_{1}\cup V_{2},f)\in{\mathcal{C}}$ with $f(a,b)=f_{i}(a,b)$ for all $i\in\{1,2\}$ and $a,b\in V_{i}$ . We say that $\mathcal{C}$ has the Joint Embedding Property (JEP) if $\operatorname{AP}(k,0,m)$ holds for all $k,m\in\mathbb{N}$ .

Theorem 18 ([6, Theorem 8]).

Let $\mathbf{A}$ be a relation algebra with $k$ atoms and let ${\mathcal{C}}$ be the class of all consistent atomic $\mathbf{A}$ -networks. Then $\mathbf{A}$ has a normal representation if and only if $\mathcal{C}$ has $\operatorname{AP}(k+1,k,k+1)$ .

Some relation algebras do not have a normal representation, but still have a fully universal representation. Such representations can be conveniently constructed with the following theorem, which is essentially due to Comer [24], but phrased there in a different formalism.

Theorem 19.

Let $\mathbf{A}$ be a finite relation algebra. Then $\mathbf{A}$ has a

$\blacksquare$

fully universal representation if and only if the class of all consistent atomic $\mathbf{A}$ -networks has AP $(3,2,n)$ for all $n$ ;
$\blacksquare$

fully universal square representation if and only if the class of all consistent atomic $\mathbf{A}$ -networks has the JEP and AP $(3,2,n)$ for all $n$ .

3 Representations for Algebras with at most 4 Atoms

In this section we revisit the representability for relation algebras with at most 4 atoms. We will show that we may focus on integral relation algebras. Exhaustive lists of integral relation algebras have been computed by Maddux [37]. There are

$\blacksquare$

2 integral relation algebras with two atoms (Table 1),
$\blacksquare$

3 integral asymmetric relation algebras with three atoms (Table 2),
$\blacksquare$

7 integral symmetric relation algebras with three atoms (Table 3),
$\blacksquare$

37 integral asymmetric relation algebras with four atoms (Table 4), and
$\blacksquare$

65 integral symmetric relation algebras with four atoms (Table 5).

It can be shown that a relation algebra is simple in the sense defined earlier if and only if it is simple in the sense of universal algebra (see, e.g., [20]). The following lemma shows that we can focus on simple relation algebras.

Lemma 20 (see, e.g., [12]).

Let $\mathfrak{B}_{1}$ be a representation of $\mathbf{A}_{1}$ and $\mathfrak{B}_{2}$ a representation of $\mathbf{A}_{2}$ , and suppose that $A_{1}\cap A_{2}=\varnothing$ and $B_{1}\cap B_{2}=\varnothing$ . Then $\mathbf{A}_{1}\times\mathbf{A}_{2}$ has a union representation, which is the $(A_{1}\times A_{2})$ -structure $\mathfrak{B}_{1}\uplus\mathfrak{B}_{2}$ with domain $B_{1}\cup B_{2}$ defined by $(a_{1},a_{2})^{\mathfrak{B}_{1}\uplus\mathfrak{B}_{2}}:=a_{1}^{\mathfrak{B}_{1% }}\cup a_{2}^{\mathfrak{B}_{2}}$ .

Example 21.

Consider the relation algebra $\mathbf{A}$ on four atoms $a, b, c, d$ , which is uniquely given by requiring $\breve{c}=d$ and the multiplication table given in Figure 1. It has a normal representation $\mathfrak{B}$ with domain $\{0,1\}$ which is given by $a^{\mathfrak{B}}=\{(0,0)\}$ , $b^{\mathfrak{B}}=\{(1,1)\}$ , $c^{\mathfrak{B}}=\{(0,1)\}$ , and $d^{\mathfrak{B}}=\{(1,0)\}$ . The algebra $\mathbf{A}$ is simple, but not integral. It is easy to see that its NSP can be solved in polynomial time. $\triangle$

It turns out that we can even restrict our attention to integral relation algebras.

Proposition 22.

The algebra from Example 21 is up to isomorphism the only simple non-integral relation algebra with at most four atoms.

$\circ$	$a$	$b$	$c$	$\breve{c}$
$a$	$a$	$0$	$0$	$\breve{c}$
$b$	$0$	$b$	$c$	$0$
$c$	$c$	$0$	$0$	$b$
$\breve{c}$	$0$	$\breve{c}$	$a$	$0$

Figure 1: Multiplication table of the simple non-integral relation algebra from Example 21.

Comer [25] states that at least 28 of the 102 integral relation algebras with four atoms are not representable. Results of Maddux [37] imply that in fact 31 do not have a representation. (And, as we have mentioned earlier, all others turn out to have a representation.)

Theorem 23.

The following 31 integral relation algebras have no representation:

$\blacksquare$

the 11 asymmetric relation algebras ${14_{37}}$ , ${16_{37}}$ , ${21_{37}}$ , ${24_{37}}$ – ${29_{37}}$ , ${32_{37}}$ , ${34_{37}}$ ;
$\blacksquare$

the 20 symmetric relation algebras ${21_{65}}$ – ${23_{65}}$ , ${35_{65}}$ – ${38_{65}}$ , ${40_{65}}$ – ${45_{65}}$ , ${47_{65}}$ – ${50_{65}}$ , ${54_{65}}$ , ${58_{65}}$ , ${60_{65}}$ .

Therefore, their $\operatorname{NSP}$ s are trivial and in $\operatorname{\mathbf{P}}$ .

Examples of finite relation algebras with a normal representation include those with a flexible atom (see, e.g., [11]).

Definition 24.

Let $\mathbf{A}$ be a relation algebra. An atom $a\in A_{0}$ is called a flexible atom if $a\leq x\circ y$ holds for all $x,y\in A_{0}\setminus\{\mathrm{Id}\}$ .

The relation algebras with a flexible atom are listed in Figure 2. Note that if a relation algebra has a flexible atom then it has a normal representation, as one can, when applying Theorem 18, always use a flexible atom for all undetermined values.

Name	Flexible Atoms	Name	Flexible Atoms
${2_{2}}$	$a$	${32_{65}}$	$a$
${3_{3}}$	$r,\breve{r}$	${33_{65}}$	$a$
${6_{7}}$	$a$	${34_{65}}$	$a$
${7_{7}}$	$a, b$	${55_{65}}$	$a$
${31_{37}}$	$a$	${57_{65}}$	$a$
${33_{37}}$	$a$	${59_{65}}$	$a$
${35_{37}}$	$a$	${61_{65}}$	$a$
${36_{37}}$	$r,\breve{r}$	${63_{65}}$	$a$
${37_{37}}$	$a,r,\breve{r}$	${64_{65}}$	$a, b$
		${65_{65}}$	$a, b, c$

Figure 2: Integral relation algebras with at most four atoms and at least one flexible atom.

With the criterion presented in Theorem 18 we verified using a computer program that the following relation algebras with at most four atoms have a normal representation:

\displaystyle\begin{split}{1_{2}},{2_{2}},{1_{3}},{2_{3}},{3_{3}},{1_{7}},{2_{% 7}},{3_{7}},{4_{7}},{6_{7}},{7_{7}},\\ {1_{37}}\text{--}{12_{37}},{15_{37}},{18_{37}}\text{--}{20_{37}},{22_{37}}% \text{--}{23_{37}},{31_{37}},{33_{37}},{35_{37}}\text{--}{37_{37}},\\ {1_{65}}\text{--}{8_{65}},{10_{65}},{11_{65}},{13_{65}},{14_{65}},{16_{65}},{1% 8_{65}}\text{--}{20_{65}},{25_{65}}\text{--}{29_{65}},\\ {32_{65}}\text{--}{34_{65}},{46_{65}},{52_{65}},{53_{65}},{55_{65}},{57_{65}},% {59_{65}},{61_{65}}\text{--}{65_{65}}.\end{split}

(3.1)

We will now discuss how representability properties of relation algebras translate to their cycle products, and apply our results to the case of integral relation algebras with four atoms.

Theorem 25 ([36, Theorem 5], see also [24]).

Let $\mathbf{A}$ and $\mathbf{B}$ be two finite representable integral relation algebras such that $A_{0}\cap B_{0}=\{\operatorname{Id}\}$ and $|A_{0}|,|B_{0}|\geq 2$ . Let $\mathfrak{C}$ and $\mathfrak{D}$ be square representations of $\mathbf{A}$ and $\mathbf{B}$ , respectively. Then $\mathbf{A}[\mathbf{B}]$ is representable and has the representation $\mathfrak{D}[\mathfrak{C}]$ on the domain $D\times C$ defined as follows. For all $a\in A_{0}\setminus\{\operatorname{Id}\},b\in B_{0}\setminus\{\operatorname{Id}\}$ :

	$\displaystyle\operatorname{Id}^{\mathfrak{D}[\mathfrak{C}]}$	$\displaystyle:=\{((u_{0},v_{0}),(u_{1},v_{1}))\mid u_{0}=u_{1},v_{0}=v_{1}\},$
	$\displaystyle a^{\mathfrak{D}[\mathfrak{C}]}$	$\displaystyle:=\{((u_{0},v_{0}),(u_{1},v_{1}))\mid u_{0}=u_{1},(v_{0},v_{1})% \in a^{\mathfrak{C}}\},$
	$\displaystyle b^{\mathfrak{D}[\mathfrak{C}]}$	$\displaystyle:=\{((u_{0},v_{0}),(u_{1},v_{1}))\mid(u_{0},u_{1})\in b^{% \mathfrak{D}}\}.$

	${1_{2}}$		${2_{2}}$
$\mathbf{A}$	${1_{2}}[\mathbf{A}]$	$\mathbf{A}[{1_{2}}]$	${2_{2}}[\mathbf{A}]$	$\mathbf{A}[{2_{2}}]$
${1_{3}}$	${1_{37}}$	${7_{37}}$	${2_{37}}$	${8_{37}}$
${2_{3}}$	${3_{37}}$	${9_{37}}$	${4_{37}}$	${10_{37}}$
${3_{3}}$	${5_{37}}$	${11_{37}}$	${6_{37}}$	${12_{37}}$
${1_{7}}$	${1_{65}}$	${1_{65}}$	${2_{65}}$	${5_{65}}$
${2_{7}}$	${3_{65}}$	${2_{65}}$	${4_{65}}$	${6_{65}}$
${3_{7}}$	${5_{65}}$	${3_{65}}$	${6_{65}}$	${7_{65}}$
${4_{7}}$	${7_{65}}$	${4_{65}}$	${8_{65}}$	${8_{65}}$
${5_{7}}$	${15_{65}}$	${9_{65}}$	${17_{65}}$	${12_{65}}$
${6_{7}}$	${16_{65}}$	${10_{65}}$	${18_{65}}$	${13_{65}}$
${7_{7}}$	${19_{65}}$	${11_{65}}$	${20_{65}}$	${14_{65}}$

Figure 3: Relation algebras formed by 2-cycle products of small relation algebras.

Lemma 26.

Let $\mathbf{A},\mathbf{B}$ be finite integral relation algebras with $A_{0}\cap B_{0}=\{\operatorname{Id}\}$ and representations $\mathfrak{C}$ and $\mathfrak{D}$ . Then

1.

if $\mathfrak{C}$ and $\mathfrak{D}$ are fully universal, then $\mathfrak{D}[\mathfrak{C}]$ is a fully universal representation of $\mathbf{A}[\mathbf{B}]$ .
2.

if $\mathfrak{C}$ and $\mathfrak{D}$ are square, then $\mathfrak{D}[\mathfrak{C}]$ is a square representation of $\mathbf{A}[\mathbf{B}]$ .
3.

if $\mathfrak{C}$ and $\mathfrak{D}$ are normal, then $\mathfrak{D}[\mathfrak{C}]$ is a normal representation of $\mathbf{A}[\mathbf{B}]$ .

To obtain a relation algebra from ${1_{37}}$ – ${37_{37}}$ as a 2-cycle product, we have to multiply an algebra from ${1_{3}}$ – ${3_{3}}$ with ${1_{2}}$ or with ${2_{2}}$ . See the first three lines of Figure 3 for all such products. Since all these algebras have a normal representation (see (3.1)), the 2-cycle product has a normal representation as well. To obtain a relation algebra from ${1_{65}}$ – ${65_{65}}$ as a 2-cycle product, we can restrict ourselves to the case where we multiply algebras from ${1_{7}}$ – ${7_{7}}$ with ${1_{2}}$ or with ${2_{2}}$ , see the last seven lines of Figure 3. Except for ${5_{7}}$ , all factors have a normal representation, so the corresponding products have a normal representation.

We are now left with relation algebras that are representable, but that do not have a normal representation. By verifying the criterion from Theorem 19, we obtain that the algebras ${13_{37}}$ , ${30_{37}}$ , ${24_{65}}$ , ${30_{65}}$ , and ${31_{65}}$ have fully universal square representations. It turns out that all remaining algebras do not have a fully universal representation. For the four algebras ${9_{65}}$ , ${12_{65}}$ , ${15_{65}}$ , and ${17_{65}}$ , this can be shown by using the fact that they can all be written as 2-cycle products with one factor being ${5_{7}}$ , which does not have a fully universal representation. ${39_{65}}$ has a square representation $\mathfrak{B}$ with 7 elements, but it has no fully universal representation. Moreover, it can be shown that all of its square representations have at most 16 elements. ${62_{65}}$ has a square representation $\mathfrak{B}$ with 13 elements, but also no fully universal representation. All square representations have at most 16 elements.

Finally, we are left with the three relation algebras ${17_{37}}$ , ${51_{65}}$ , and ${56_{65}}$ , which have infinite square representations, but no fully universal ones. For the first two of them, we even obtain the following stronger results.

Theorem 27.

There is a consistent, but unsatisfiable atomic ${17_{37}}$ -network $N$ on four vertices and a square representation $\mathfrak{B}$ of ${17_{37}}$ such that a consistent atomic ${17_{37}}$ -network is satisfiable in $\mathfrak{B}$ if and only if it does not have $N$ as a subnetwork.

Theorem 28.

There are four consistent, but unsatisfiable atomic ${51_{65}}$ -networks $N_{1}$ , $N_{2}$ , $N_{3}$ , and $N_{4}$ on four vertices and a square representation $\mathfrak{B}$ of ${51_{65}}$ such that a consistent atomic ${51_{65}}$ -network is satisfiable in $\mathfrak{B}$ if and only if it has none of $N_{1}$ , $N_{2}$ , $N_{3}$ , and $N_{4}$ as a subnetwork.

4 NP-hard Algebras with at most 4 Atoms

In this section we present $\operatorname{\mathbf{NP}}$ -hardness results for relation algebras with at most 4 atoms. If the relation algebra has a normal representation, it falls into the scope of the tractability conjecture (Conjecture 1.1), and we provide a pp-construction of $(\{0,1\};\operatorname{NAE})$ in each of these cases. For the relation algebras with at most 3 atoms, a classification has already been established in [26], with two corrections in [10]; in particular, ${6_{7}}$ is $\operatorname{\mathbf{NP}}$ -complete. For the relation algebras with 4 atoms, the NSP for ${15_{37}}$ has been shown to be $\operatorname{\mathbf{NP}}$ -complete by Broxvall and Jonsson [17]; by inspecting their proof, it is not difficult to obtain a pp-interpretation of $(\{0,1\};\operatorname{NAE})$ in the normal representation of ${15_{37}}$ , confirming the tractability conjecture in this case. The remaining hardness proofs are grouped according to the applied proof method.

The $\operatorname{\mathbf{NP}}$ -completeness of the $\operatorname{NSP}({39_{65}})$ and $\operatorname{NSP}({62_{65}})$ follows from our representability results together with the following lemma:

Lemma 29.

Let $\mathbf{A}$ be a finite simple relation algebra such that the maximum cardinality of all square representations of $\mathbf{A}$ equals $n\in\mathbb{N}$ . Then $\operatorname{NSP}(\mathbf{A})$ is in $\operatorname{\mathbf{NP}}$ . If $\mathbf{A}$ additionally has a square representation with at least three elements, then $\operatorname{NSP}(\mathbf{A})$ is $\operatorname{\mathbf{NP}}$ -complete.

The network satisfaction problem for finite symmetric relation algebras with a flexible atom is in $\operatorname{\mathbf{P}}$ or $\operatorname{\mathbf{NP}}$ -complete [11]. The tractability conjecture (Conjecture 1.1) has already been confirmed for this case (compare to [12, Theorem 9.1]). To determine which of the two cases applies in the concrete cases, we need the following propositions.

Proposition 30 ([11, Theorem 2.21 and Proposition 6.1]).

Let $\mathbf{A}$ be a finite, symmetric, integral relation algebra with a flexible atom and $\mathfrak{B}$ a normal representation of $\mathbf{A}$ . If $\mathfrak{B}$ does not have a binary injective polymorphism, then $\operatorname{CSP}(\mathfrak{B})$ is $\operatorname{\mathbf{NP}}$ -complete.

Proposition 31 ([12, Lemma 4.3]).

Let $\mathbf{A}$ be a finite symmetric relation algebra with a normal representation $\mathfrak{B}$ that has a binary injective polymorphism. Then $(p,p,p)$ is an allowed triple of $\mathbf{A}$ for all $p\in\mathbf{A}$ .

The relation algebras ${32_{65}}$ , ${33_{65}}$ , ${55_{65}}$ , ${57_{65}}$ , ${59_{65}}$ , ${63_{65}}$ , and ${64_{65}}$ are all symmetric, have a flexible atom (see Figure 2), but contain an element $p$ such that $(p,p,p)$ is a forbidden triple. Thus, they have no binary injective polymorphism by Proposition 31, and therefore, by Proposition 30, their NSPs are $\operatorname{\mathbf{NP}}$ -complete. The algebra ${34_{65}}$ is symmetric and has a flexible atom too. It can be shown that its atom structure has an $\operatorname{\mathbf{NP}}$ -complete CSP, which implies that $\operatorname{NSP}({34_{65}})$ is $\operatorname{\mathbf{NP}}$ -complete as well due to the following theorem:

Theorem 32 ([11, Theorem 9.1]).

Let $\mathbf{A}$ be a finite symmetric relation algebra with a flexible atom and atom structure $\mathfrak{A}_{0}$ . Then $\operatorname{CSP}(\mathfrak{A}_{0})$ and $\operatorname{NSP}(\mathbf{A})$ are polynomial-time equivalent.

An equivalence relation $E\subseteq B^{2}$ is called proper if $E$ is a proper subset of $B^{2}$ ; it is called trivial if it is the equality relation on $B$ , and non-trivial otherwise. The algebras ${3_{37}}$ , ${4_{37}}$ , ${7_{37}}$ , ${9_{37}}$ , ${11_{37}}$ , ${18_{37}}$ , ${20_{37}}$ , ${1_{65}}$ , ${2_{65}}$ , ${3_{65}}$ , ${4_{65}}$ , ${10_{65}}$ , ${11_{65}}$ , ${25_{65}}$ , ${26_{65}}$ , and ${28_{65}}$ all have a normal representation $\mathfrak{B}$ and a non-trivial proper equivalence relation $e$ such that $e^{\mathfrak{B}}$ has only finitely many classes. Hence, their NSPs are $\operatorname{\mathbf{NP}}$ -complete by the following theorem:

Theorem 33 ([10, Theorem 23]).

Let $\mathbf{A}$ be a finite relation algebra with normal representation $\mathfrak{B}$ and a non-trivial proper equivalence relation $e\in A$ such that $e^{\mathfrak{B}}$ has only finitely many classes. Then $\operatorname{CSP}(\mathfrak{B})$ is $\operatorname{\mathbf{NP}}$ -complete.

Next, we consider algebras which do not contain a non-trivial proper equivalence relation. A permutation group is called primitive if it does not preserve a non-trivial proper equivalence relation. Note that if $\mathbf{A}$ is a finite relation algebra with a normal representation $\mathfrak{B}$ , then $\operatorname{Aut}(\mathfrak{B})$ is primitive if and only if $\mathbf{A}$ does not contain equivalence relations besides $1$ and $\operatorname{Id}$ .

Using the following theorem, we obtain $\operatorname{\mathbf{NP}}$ -completeness for the NSPs of ${23_{37}}$ , ${36_{37}}$ , and ${46_{65}}$ .

Theorem 34 ([10, Theorem 29]).

Let $\mathbf{A}$ be a relation algebra with a normal representation $\mathfrak{B}$ . If $\operatorname{Aut}(\mathfrak{B})$ is primitive and $a\in A_{0}$ is symmetric such that $(a,a,a)$ is forbidden in $\mathbf{A}$ , then $\operatorname{CSP}(\mathfrak{B})$ and $\operatorname{NSP}(\mathbf{A})$ are $\operatorname{\mathbf{NP}}$ -complete.

The proofs of Theorem 33 and 34 in [10] already confirm the tractability conjecture (Conjecture 1.1) in all cases which we considered.

The following lemmas imply that if a relation algebra is a 2-cycle product of two relation algebras $\mathbf{A}$ and $\mathbf{B}$ , and $\mathbf{A}$ or $\mathbf{B}$ has an $\operatorname{\mathbf{NP}}$ -complete NSP, then the network satisfaction problem for the 2-cycle product has an $\operatorname{\mathbf{NP}}$ -complete NSP as well.

Lemma 35.

Let $\mathbf{A}$ and $\mathbf{B}$ be finite relation algebras such that $\operatorname{NSP}(\mathbf{A})$ and $\operatorname{NSP}(\mathbf{B})$ are both in $\operatorname{\mathbf{NP}}$ . Then $\operatorname{NSP}(\mathbf{A}[\mathbf{B}])$ is in $\operatorname{\mathbf{NP}}$ as well.

Lemma 36.

Let $\mathbf{A}$ and $\mathbf{B}$ be finite representable relation algebras such that $A_{0}\cap B_{0}=\{\operatorname{Id}\}$ . Then there is a polynomial-time reduction from $\operatorname{NSP}(\mathbf{A})$ to $\operatorname{NSP}(\mathbf{A}[\mathbf{B}])$ and from $\operatorname{NSP}(\mathbf{B})$ to $\operatorname{NSP}(\mathbf{A}[\mathbf{B}])$ . If $\mathfrak{A}$ and $\mathfrak{B}$ are normal representations of $\mathbf{A}$ and $\mathbf{B}$ , respectively, then $\mathfrak{B}[\mathfrak{A}]$ pp-constructs $\mathfrak{A}$ and $\mathfrak{B}$ .

From these two lemmas and Table 3 we infer the $\operatorname{\mathbf{NP}}$ -completeness of the NSPs of ${10_{37}}$ , ${5_{65}}$ , ${6_{65}}$ , ${9_{65}}$ , ${12_{65}}$ , ${13_{65}}$ , ${15_{65}}$ , ${16_{65}}$ , ${17_{65}}$ , and ${18_{65}}$ and confirm the tractability conjecture for those among them that have a normal representation.

We prove the $\operatorname{\mathbf{NP}}$ -hardness of seven NSPs by means of pp-interpretations. For the algebras ${19_{37}}$ , ${27_{65}}$ , and ${29_{65}}$ , it can be inferred from the nonexistence of certain polymorphisms that the respective normal representation pp-interprets $(\{0,1\};\mathrm{NAE})$ ; the argument is summarized in the following proposition.

Let $\mathfrak{B}$ be a normal representation of a finite relation algebra $\mathbf{A}$ and $X\subseteq A_{0}$ . An operation $f\colon B^{n}\to B$ is called $X$ -canonical (with respect to $\mathfrak{B}$ ) if there exists a function $\overline{f}\colon X^{n}\to A_{0}$ such that for all $x,y\in B^{n}$ and $a_{1},\dots,a_{n}\in X$ , if $(x_{i},y_{i})\in a_{i}^{\mathfrak{B}}$ for all $i\in\{1,\dots,n\}$ , then $(f(x),f(y))\in\overline{f}(a_{1},\dots,a_{n})^{\mathfrak{B}}$ . The function $\overline{f}$ is called the behaviour of $f$ on $X$ .

Proposition 37.

Let $\mathbf{A}$ be a finite relation algebra with a normal representation $\mathfrak{B}$ . If there are two distinct elements $x,y\in A_{0}$ such that every polymorphism $f$ of $\mathfrak{B}$ is $\{x,y\}$ -canonical, but its behaviour on $\{x,y\}$ is not a binary symmetric, a ternary majority, or a ternary minority operation, then $\operatorname{NSP}(\mathbf{A})$ is $\operatorname{\mathbf{NP}}$ -complete.

We take a different approach for the two hardness proofs of $\operatorname{NSP}({33_{37}})$ and $\operatorname{NSP}({35_{37}})$ , in which we directly give a pp-interpretation of a structure with $\operatorname{\mathbf{NP}}$ -hard CSP in the normal representation of the respective relation algebra.

Let $\mathbb{H}=(V;E)$ be the Henson graph, i.e., the countable homogeneous graph whose age is the class of all finite undirected triangle-free graphs. We obtain a (normal) representation $\mathfrak{B}=\mathbb{H}^{b,a}$ of ${6_{7}}$ : we set $b^{\mathfrak{B}}:=E$ , $a^{\mathfrak{B}}:=\{(u,v)\in V^{2}\setminus E\mid u\neq v\}$ , $\operatorname{Id}^{\mathfrak{B}}:=\{(u,v)\in V^{2}\mid u=v\}$ , and extend to all other relations by taking the respective Boolean combinations. It is known that $\operatorname{NSP}({6_{7}})$ is $\operatorname{\mathbf{NP}}$ -complete [10]. By a reduction from $\operatorname{CSP}(\mathbb{H})$ , we obtain that the normal representations of ${31_{37}}$ and ${52_{65}}$ pp-construct $(\{0,1\};\operatorname{NAE})$ ; consequently, $\operatorname{NSP}({31_{37}})$ and $\operatorname{NSP}({52_{65}})$ are $\operatorname{\mathbf{NP}}$ -complete.

The algebras ${30_{65}}$ , ${30_{37}}$ , and ${31_{65}}$ do not have a normal representation and hence do not fall within the scope of the tractability conjecture. We show the $\operatorname{\mathbf{NP}}$ -hardness of their NSPs by many-one reductions from again the Henson graph and from $\operatorname{\mathbf{NP}}$ -hard Boolean satisfiability problems.

As we have seen (Theorem 28), the algebra ${51_{65}}$ has a universal representation, which is obtained by excluding four atomic networks that are consistent but unsatisfiable; it follows that the NSP is in $\operatorname{\mathbf{NP}}$ , and in fact it is $\operatorname{\mathbf{NP}}$ -complete. The algebra ${56_{65}}$ is similar to the previous one, but allows one extra triple compared to ${51_{65}}$ . Its NSP is $\operatorname{\mathbf{NP}}$ -hard as well; proving the containment of the NSP in $\operatorname{\mathbf{NP}}$ turns out to be challenging and was published separately (see [8]). We obtain the $\operatorname{\mathbf{NP}}$ -hardness of $\operatorname{NSP}({51_{65}})$ and $\operatorname{NSP}({56_{65}})$ as a corollary of the following new technique based on a recent hardness result from the area of promise constraint satisfaction problems [19].

Proposition 38.

Let $\mathbf{A}$ be a representable finite relation algebra with two symmetric atoms $p, q$ such that $(p,p,p)$ and $(q,q,q)$ are forbidden and $(p,q,q)$ is an allowed triple. Then $\operatorname{NSP}(\mathbf{A})$ is $\operatorname{\mathbf{NP}}$ -hard.

$\blacktriangleright$ Remark 39.

This method also shows that the NSP for each of the algebras ${1_{7}}$ , ${5_{7}}$ , ${1_{65}}$ , ${2_{65}}$ , ${5_{65}}$ , ${10_{65}}$ , ${12_{65}}$ , ${15_{65}}$ , ${16_{65}}$ , ${17_{65}}$ , ${39_{65}}$ , ${55_{65}}$ , ${62_{65}}$ , and ${63_{65}}$ is $\operatorname{\mathbf{NP}}$ -hard (which was already established earlier), since each of them is representable and has two atoms satisfying the condition of Proposition 38.

5 Tractable Algebras with at most 4 Atoms

We present polynomial-time algorithms for the network satisfaction problem for all the remaining integral relation algebras with at most four atoms.

Let $\mathfrak{A}_{0}$ be the atom structure of a relation algebra $\mathbf{A}$ that has a fully universal representation. The following implies that if $\operatorname{CSP}(\mathfrak{A}_{0})$ is in $\operatorname{\mathbf{P}}$ , then so is $\operatorname{NSP}(\mathbf{A})$ .

Proposition 40 ([12, Proposition 2.16]).

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

The good news here is that there is a complete complexity classification of finite domain CSPs, as we mentioned in the introduction; the bad news is that $\operatorname{CSP}(\mathfrak{A}_{0})$ might be $\operatorname{\mathbf{NP}}$ -complete, while $\operatorname{NSP}(\mathbf{A})$ is still in $\operatorname{\mathbf{P}}$ ; this happens for instance for the point algebra ${1_{3}}$ [41] and will later force us to treat some cases separately. But first, we will make use of Proposition 40 via the following lemma:

Lemma 41.

Let $\mathbf{A}$ be a relation algebra with a fully universal representation and atom structure $\mathfrak{A}_{0}$ . If $\mathfrak{A}_{0}$ has a polymorphism $f$ which is binary symmetric or a ternary weak near unanimity operation, then $\operatorname{NSP}(\mathbf{A})$ is in $\operatorname{\mathbf{P}}$ .

The atom structures of the algebras ${1_{2}}$ , ${2_{2}}$ , ${4_{7}}$ , ${7_{7}}$ , ${8_{65}}$ , ${14_{65}}$ , ${20_{65}}$ , ${53_{65}}$ , ${61_{65}}$ , and ${65_{65}}$ all have a binary symmetric polymorphism; hence, the NSPs of those algebras are in $\operatorname{\mathbf{P}}$ . For the algebras ${3_{3}}$ , ${3_{7}}$ , ${5_{37}}$ , ${6_{37}}$ , ${12_{37}}$ , ${22_{37}}$ , ${37_{37}}$ , ${7_{65}}$ , and ${19_{65}}$ , we obtain tractability of their NSPs since their respective atom structures all have a ternary weak near unanimity polymorphism; for ${3_{7}}$ , this was already shown in [14].

A particularly natural polynomial-time algorithm in the context of the network consistency problem and the network satisfaction problem for a fixed relation algebra $\mathbf{A}$ is the path consistency algorithm. It takes as input an $\mathbf{A}$ -network $(V,f)$ and repeatedly considers three variables $u, v, w$ and updates $f(u,v)$ by intersecting it with $f(u,w)\circ f(w,v)$ . The NSPs of ${1_{37}}$ , ${2_{37}}$ , and ${8_{37}}$ can be solved by the path consistency procedure, and are thus polynomial-time tractable.

We are left with the two algebras ${24_{65}}$ and ${17_{37}}$ , which turn out to have polynomial-time tractable NSPs as well. Our algorithms for them are more involved and make use of structural results about consistent ${24_{65}}$ - and ${17_{37}}$ -networks, respectively, to solve their NSPs by a divide-and-conquer approach. The algebra ${17_{37}}$ is related to the class of quasi-transitive oriented graphs, which has been studied in graph theory [2]. As we have mentioned, it has a universal square representation, which is obtained by excluding a single consistent, but unsatisfiable atomic network on four vertices (Theorem 27); this representation is in turn closely related to series-parallel partial orders. We discuss the NSP of ${24_{65}}$ in the following section and refer to the long version of the paper for ${17_{37}}$ .

5.1 The Relation Algebra ${24_{65}}$

The algebra ${24_{65}}$ has four symmetric atoms $\operatorname{Id},a,b,c$ and $(a,b,c)$ as forbidden triple. It is related to the class of 3-edge-coloured cliques with no rainbow triangle, which exhibits interesting combinatorics, and has a fully universal representation.

We need the following facts about consistent atomic ${24_{65}}$ -networks $(V,f)$ . If $d\in\{a,b,c\}$ , let $G_{d}$ be the graph $G_{d}:=(V;\{(x,y)\mid f(x,y)\in\{d,\operatorname{Id}\}\})$ . The following is straightforward.

Lemma 42.

Let $(V,f)$ be a consistent atomic ${24_{65}}$ -network. If $C_{1}$ and $C_{2}$ are different connected components of $G_{d}$ , for some $d\in\{a,b,c\}$ , then $f$ is constant on all pairs $(x,y)$ for $x\in C_{1}$ and $y\in C_{2}$ .

The following lemma is due to Sebastian Meyer (personal communication).

Lemma 43.

Let $(V,f)$ be a consistent atomic ${24_{65}}$ -network such that the image of $f$ is not $\{\operatorname{Id}\}$ . Then at least one of the graphs $G_{a}$ , $G_{b}$ , and $G_{c}$ is disconnected.

Note that all relations of the relation algebra ${24_{65}}$ can be generated from the following relations: $\overline{\operatorname{Id}}=a\cup b\cup c$ and $R_{d}:=(d\cup\operatorname{Id})$ for $d\in\{a,b,c\}$ . For example, $\overline{a}=R_{b}\circ R_{c}$ . Similarly we can obtain $\overline{b}$ and $\overline{c}$ . We can then obtain all others by appropriately intersecting the ones that we already have. It therefore suffices to present an algorithm for the NSP restricted to networks with the relations ${\mathcal{R}}:=\{R_{a},R_{b},R_{c},\overline{\operatorname{Id}},\operatorname{% Id},1\}$ (see the long version of the paper for details).

Definition 44.

Let $(V,g)$ be a ${24_{65}}$ -network such that the image of $g$ is contained in $\mathcal{R}$ and let $d\in\{a,b,c\}$ . A $d$ -cut of $(V,g)$ is a partition of $V$ into $k\geq 2$ disjoint sets $C_{1},\dots,C_{k}$ such that if $g(x,y)\in\{R_{d},\operatorname{Id}\}$ , then $x$ and $y$ must lie in the same part. A $d$ -cut is valid if for all distinct $i,j\in\{1,\dots,k\}$ there exists $d_{i,j}\in\{a,b,c\}\setminus\{d\}$ such that $d_{i,j}\leq g(u,x)$ for all $u\in C_{i}$ and $x\in C_{j}$ .

Definition 45.

A non-identity solution to an $\mathbf{A}$ -network $(V,g)$ is a solution $(V,f)$ such that there are $x,y\in V$ with $f(x,y)\neq\operatorname{Id}$ .

Lemma 46.

Let $(V,g)$ be a ${24_{65}}$ -network such that $(V,g)$ has a non-identity solution and the image of $g$ is contained in $\mathcal{R}$ . Then there is a valid $d$ -cut in $(V,g)$ for some $d\in\{a,b,c\}$ .

Proof.

Let $(V,f)$ be a non-identity solution of $(V,g)$ . By Lemma 43, there exists $d\in\{a,b,c\}$ such that $G_{d}$ is disconnected. Let $C_{1},\dots,C_{k}\subseteq V$ be the connected components of $G_{d}$ . Clearly, it is a $d$ -cut of $(V,g)$ . Lemma 42 implies that it is valid. $\hfill\blacktriangleleft$

Note that the condition from Lemma 46 can be checked in polynomial time: to check whether $(V,g)$ has a valid $d$ -cut, we first compute the connected components of the graph $(V;\{(x,y)\mid g(x,y)\in\{R_{d},\operatorname{Id}\}\})$ (e.g., via depth-first search). If the connected components provide a valid $d$ -cut we are done. Otherwise, there exist two components $C_{i}$ and $C_{j}$ that witness that the cut is not valid. In this case, we merge $C_{i}$ and $C_{j}$ into one component. If the resulting $d$ -cut is valid, we are done. Otherwise, we repeat contracting components. If the procedure ends up with a single component, then there does not exist a valid $d$ -cut.

Proposition 47.

$\operatorname{NSP}({24_{65}})$ is in $\operatorname{\mathbf{P}}$ .

Proof.

Let $(V,g)$ be a given ${24_{65}}$ -network. As we have explained earlier, we may assume without loss of generality that the image of $g$ is contained in $\mathcal{R}$ .

1.

If there is no pair of variables labelled $\overline{\operatorname{Id}}$ , then answer “satisfiable” (we may map all of $V$ to the same point in a representation of ${24_{65}}$ ).
2.

Otherwise, if for every $d\in\{a,b,c\}$ there is no valid $d$ -cut in $(V,g)$ return “unsatisfiable” (there is no solution by Lemma 46).
3.

Otherwise, let $C_{1},\dots,C_{k}$ be a valid $d$ -cut in $(V,g)$ , for some $d\in\{a,b,c\}$ , and recursively solve the subinstances induced on each of $C_{1},\dots,C_{k}$ .
4.

If a recursive call returns “unsatisfiable”, then return “unsatisfiable”.
5.

Otherwise, return “satisfiable” (a consistent atomic network $(V,f)$ with $f(x,y)\leq g(x,y)$ for all $x,y\in V$ can be obtained from solutions for $C_{1},\dots,C_{k}$ by setting $f(x,y):=d_{i,j}$ for every $x\in C_{i}$ and $y\in C_{j}$ with $i\neq j$ ).

The proof that this algorithm is correct follows by induction on the number of variables of the instance. The running time is in $O(n^{2})$ if $n$ is the size of the input. $\hfill\blacktriangleleft$

6 Open Problems

We view our complexity dichotomy for the network satisfaction problem for relation algebras with at most 16 elements as an encouraging basis for a more general classification result without any restriction on the number of elements for the finite relation algebras with a normal (or even just fully universal) representation. The following other problems are also left open.

Question 47.

Is the existence of a fully universal representation for a given finite relation algebra effectively decidable?

Question 47.

What is the smallest relation algebra $\mathbf{A}$ such that $\operatorname{NSP}(\mathbf{A})$ is not in $\operatorname{\mathbf{NP}}$ ?

The network consistency problem (NCP) of a relation algebra $\mathbf{A}$ is the following computational problem: Its input is an $\mathbf{A}$ -network $(V,f)$ . The task is to decide whether there exists a consistent atomic network $(V,s)$ (which will also be called the solution to the given problem instance) on the same set of vertices $V$ such that for all $x,y\in V$ we have $s(x,y)\leq f(x,y)$ . Unlike the network satisfaction problem of a finite relation algebra $\mathbf{A}$ , which can be undecidable [31], the network consistency problem for $\mathbf{A}$ is always in $\operatorname{\mathbf{NP}}$ . For relation algebras with a fully universal representation, the NSP and the NCP have the same complexity, whereas for other algebras, additional efforts are required; e.g., if $\mathbf{A}$ has no representation, then $\operatorname{NSP}(\mathbf{A})$ is trivial, whereas $\operatorname{NCP}(\mathbf{A})$ is generally not.

Problem 47.

Obtain a similar classification for the network consistency problem.

Problem 47.

Obtain a similar classification for the variant of the network satisfaction problem where the inputs are restricted to networks $(V,f)$ such that the range of $f$ consists only of atoms and $1$ .

References

[1] Hajnal Andréka and Roger D. Maddux. Representations for small relation algebras. Notre Dame Journal of Formal Logic, 35(4):550–562, 1994. doi:10.1305/NDJFL/1040408612.
[2] Jørgen Bang-Jensen and Jing Huang. Quasi-transitive digraphs. Journal of Graph Theory, 20(2):141–161, 1995. doi:10.1002/jgt.3190200205.
[3] Libor Barto, Michael Kompatscher, Miroslav Olšák, Trung Van Pham, and Michael Pinsker. The equivalence of two dichotomy conjectures for infinite domain constraint satisfaction problems. In Proceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science – LICS’17, 2017. Preprint arXiv:1612.07551. arXiv:1612.07551.
[4] Libor Barto, Jakub Opršal, and Michael Pinsker. The wonderland of reflections. Israel Journal of Mathematics, 223(1):363–398, 2018.
[5] Libor Barto and Michael Pinsker. The algebraic dichotomy conjecture for infinite domain constraint satisfaction problems. In Proceedings of the 31st Annual IEEE Symposium on Logic in Computer Science – LICS’16, pages 615–622, 2016. Preprint arXiv:1602.04353. arXiv:1602.04353.
[6] 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. doi:10.1007/978-3-030-02149-8_1.
[7] Manuel Bodirsky. Complexity of Infinite-Domain Constraint Satisfaction. Lecture Notes in Logic (52). Cambridge University Press, Cambridge, United Kingdom; New York, NY, 2021. doi:10.1017/9781107337534.
[8] Manuel Bodirsky, Santiago Guzmán-Pro, Moritz Jahn, Matěj Konečný, and Paul Winkler. Circular chromatic numbers, balanceability, relation algebras, and network satisfaction problems, 2025. Preprint available under https://arxiv.org/abs/2512.06878. doi:10.48550/arXiv.2512.06878.
[9] Manuel Bodirsky and Jan Kára. The complexity of temporal constraint satisfaction problems. Journal of the ACM, 57(2):1–41, 2009. An extended abstract appeared in the Proceedings of the Symposium on Theory of Computing (STOC). doi:10.1145/1667053.1667058.
[10] 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. doi:10.1007/978-3-030-43520-2_3.
[11] 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, 2022. doi:10.1613/jair.1.14195.
[12] Manuel Bodirsky and Simon Knäuer. Network satisfaction problems solved by $k$ -consistency. In 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023, July 10-14, 2023, Paderborn, Germany, pages 116:1–116:20, 2023. doi:10.4230/LIPIcs.ICALP.2023.116.
[13] Manuel Bodirsky and Martin Kutz. Pure dominance constraints. In Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS), pages 287–298, 2002. doi:10.1007/3-540-45841-7_23.
[14] Manuel Bodirsky, Barnaby Martin, Michael Pinsker, and András Pongrácz. Constraint satisfaction problems for reducts of homogeneous graphs. SIAM Journal on Computing, 48(4):1224–1264, 2019. A conference version appeared in the Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, pages 119:1-119:14. doi:10.1137/16M1082974.
[15] Manuel Bodirsky and Michael Pinsker. Schaefer’s theorem for graphs. Journal of the ACM, 62(3):52 pages (article number 19), 2015. A conference version appeared in the Proceedings of STOC 2011, pages 655-664. doi:10.1145/2764899.
[16] Manuel Bodirsky, Michael Pinsker, and András Pongrácz. Projective clone homomorphisms. Journal of Symbolic Logic, 86(1):148–161, 2021. doi:10.1017/JSL.2019.23.
[17] Mathias Broxvall and Peter Jonsson. Point algebras for temporal reasoning: Algorithms and complexity. Artificial Intelligence, 149(2):179–220, 2003. doi:10.1016/S0004-3702(03)00075-4.
[18] 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. doi:10.1109/FOCS.2017.37.
[19] Jakub Bulín, Andrei A. Krokhin, and Jakub Opršal. Algebraic approach to promise constraint satisfaction. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 602–613, 2019. doi:10.1145/3313276.3316300.
[20] Stanley N. Burris and Hanamantagouda P. Sankappanavar. A Course in Universal Algebra. Springer Verlag, Berlin, 1981.
[21] Peter J. Cameron. The random graph. R. L. Graham and J. Nešetřil, Editors, The Mathematics of Paul Erdös, 1996.
[22] Gregory Cherlin. Homogeneous ordered graphs and metrically homogeneous graphs, 2020. Preprint.
[23] Gregory L. Cherlin. The classification of countable homogeneous directed graphs and countable homogeneous $n$ -tournaments. AMS Memoir, 131(621), January 1998.
[24] Stephen D. Comer. Extension of polygroups by polygroups and their representations using color schemes. In Ralph S. Freese and Octavio C. Garcia, editors, Universal Algebra and Lattice Theory, pages 91–103, Berlin, Heidelberg, 1983. Springer Berlin Heidelberg.
[25] Stephen D. Comer. A remark on chromatic polygroups. Congressus Numerantium, 38:85–95, 1983.
[26] Matteo Cristiani and Robin Hirsch. The complexity of the constraint satisfaction problem for small relation algebras. Artificial Intelligence Journal, 156:177–196, 2004. doi:10.1016/J.ARTINT.2004.02.003.
[27] Michael Garey and David Johnson. A guide to NP-completeness. CSLI Press, Stanford, 1978.
[28] C. Ward Henson. Countable homogeneous relational systems and categorical theories. Journal of Symbolic Logic, 37:494–500, 1972.
[29] R. Hirsch and I. Hodkinson. Representability is not decidable for finite relation algebras. Transactions of the American Mathematical Society, 353(4):1387–1401, 2001.
[30] Robin Hirsch. Relation algebras of intervals. Artificial Intelligence Journal, 83:1–29, 1996.
[31] Robin Hirsch. A finite relation algebra with undecidable network satisfaction problem. Logic Journal of the IGPL, 7(4):547–554, 1999. doi:10.1093/JIGPAL/7.4.547.
[32] Wilfrid Hodges. A shorter model theory. Cambridge University Press, Cambridge, 1997.
[33] Alistair H. Lachlan and Robert E. Woodrow. Countable ultrahomogeneous undirected graphs. Transactions of the AMS, 262(1):51–94, 1980.
[34] Richard E. Ladner. On the structure of polynomial time reducibility. Journal of the ACM, 22(1):155–171, 1975. doi:10.1145/321864.321877.
[35] R. Lyndon. The representation of relational algebras. Annals of Mathematics, 51(3):707–729, 1950.
[36] Roger D. Maddux. Finite symmetric integral relation algebras with no 3-cycles. In Renate A. Schmidt, editor, Relations and Kleene Algebra in Computer Science, 9th International Conference on Relational Methods in Computer Science and 4th International Workshop on Applications of Kleene Algebra, RelMiCS/AKA 2006, Manchester, UK, August 29-September 2, 2006, Proceedings, volume 4136 of Lecture Notes in Computer Science, pages 2–29. Springer, 2006. doi:10.1007/11828563_2.
[37] Roger Duncan Maddux. Relation Algebras: Volume 150. Studies in logic and the foundations of mathematics. Elsevier Science, London, England, May 2006.
[38] Donald Monk. On representable relation algebras. Michigan Mathematical Journal, 11(3):207–210, 1964. doi:10.1307/mmj/1028999131.
[39] Alfred Tarski. On the calculus of relations. J. Symbolic Logic, 6, 1941. doi:10.2307/2268577.
[40] Alfred Tarski. Contributions to the theory of models. Koninklijke Nederlandse Akademie van Wetenschappen, Proceedings, 58:56–64, 1955.
[41] Marc Vilain, Henry Kautz, and Peter van Beek. Constraint propagation algorithms for temporal reasoning: A revised report. Reading in Qualitative Reasoning about Physical Systems, pages 373–381, 1989.
[42] Dmitriy Zhuk. A proof of the CSP dichotomy conjecture. J. ACM, 67(5):30:1–30:78, 2020. doi:10.1145/3402029.
[43] 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. arXiv:1704.01914.
[44] Paul-Hermann Zieschang. Hypergroups. Springer, 2023.

Appendix A Appendix

In Tables 1–5, we present Maddux’s lists of integral relation algebras, together with references and comments about their representability and the computational complexity of their network satisfaction problem, thus summarizing the findings of the previous sections. The first column is the numbering introduced by Maddux. The following columns are labelled by triples (omitting brackets and commas for space reasons). An entry of the table contains the triple if it is an allowed triple of the relation algebra; this uniquely describes the relation algebra.

In the tables, we use the following abbreviations:

$\blacksquare$

none: no representation exists
$\blacksquare$

$\neg$ f.u.: the relation algebra is representable, but there is no fully universal representation.
$\blacksquare$

f.u.: there exists a fully universal square representation, but no normal representation.
$\blacksquare$

normal: there exists a normal representation, but the algebra has no flexible atom.
$\blacksquare$

flex: there is a flexible atom (which implies the existence of a normal representation).

In [10] it has been noted that in the case of $2_{7}$ and $6_{7}$ the claims about the complexity of the NSP from [26] are incorrect, and we state the corrected results.

Table 1: Integral relation algebras with two atoms.

$\#_{2}$	$a a a$	Representability	NSP Complexity
$1_{2}$		normal	$\operatorname{\mathbf{P}}\nobreak\ \text{\cite[cite]{[\@@bibref{}{% HirschCristiani}{}{}]}}$
$2_{2}$	$a a a$	flex	$\operatorname{\mathbf{P}}\nobreak\ \text{\cite[cite]{[\@@bibref{}{% HirschCristiani}{}{}]}}$

Table 2: Integral asymmetric relation algebras with three atoms.

$\#_{3}$	$r r r$	$rr\breve{r}$	Representability	NSP Complexity
$1_{3}$	$r r r$		normal	$\operatorname{\mathbf{P}}\nobreak\ \text{\cite[cite]{[\@@bibref{}{PointAlgebra% }{}{}]}}$
$2_{3}$		$rr\breve{r}$	normal	$\operatorname{\mathbf{NPc}}\nobreak\ \cite[cite]{[\@@bibref{}{HirschCristiani}% {}{}]}$
$3_{3}$	$r r r$	$rr\breve{r}$	flex	$\operatorname{\mathbf{P}}\nobreak\ \text{\cite[cite]{[\@@bibref{}{% HirschCristiani}{}{}]}}$

Table 3: Integral symmetric relation algebras with three atoms.

$\#_{7}$	$a a a$	$b b b$	$a b b$	$b a a$	Representability	NSP Complexity
$1_{7}$			$a b b$		normal	$\operatorname{\mathbf{NPc}}\nobreak\ \cite[cite]{[\@@bibref{}{HirschCristiani}% {}{}]}$
$2_{7}$	$a a a$		$a b b$		normal	$\operatorname{\mathbf{NPc}}\nobreak\ \cite[cite]{[\@@bibref{}{% BodirskyKnaeRamics}{}{}]}$
$3_{7}$		$b b b$	$a b b$		normal	$\operatorname{\mathbf{P}}\nobreak\ \cite[cite]{[\@@bibref{}{HirschCristiani}{}% {}]}$
$4_{7}$	$a a a$	$b b b$	$a b b$		normal	$\operatorname{\mathbf{P}}\nobreak\ \cite[cite]{[\@@bibref{}{HirschCristiani}{}% {}]}$
$5_{7}$			$a b b$	$b a a$	$\neg\text{f.u.}$	$\operatorname{\mathbf{NPc}}\nobreak\ \cite[cite]{[\@@bibref{}{HirschCristiani}% {}{}]}$
$6_{7}$	$a a a$		$a b b$	$b a a$	flex	$\operatorname{\mathbf{NPc}}\nobreak\ \cite[cite]{[\@@bibref{}{% BodirskyKnaeRamics}{}{}]}$
$7_{7}$	$a a a$	$b b b$	$a b b$	$b a a$	flex	$\operatorname{\mathbf{P}}\nobreak\ \text{\cite[cite]{[\@@bibref{}{% HirschCristiani}{}{}]}}$

Table 4: The relation algebras

1_{37}

–

37_{37}

with the four atoms

a,r,\breve{r},\operatorname{Id}

, where

a

is symmetric and

r

is non-symmetric, representability information, and complexity of their NSP.

${\#_{37}}$	$a a a$	$r r r$	$rr\breve{r}$	$a r r$	$r a r$	$r a a$	$r r a$	Representation	NSP Complexity
$1_{37}$		$r r r$		$a r r$	$r a r$			normal	$\operatorname{\mathbf{P}}$
$2_{37}$	$a a a$	$r r r$		$a r r$	$r a r$			normal	$\operatorname{\mathbf{P}}$
$3_{37}$			$rr\breve{r}$	$a r r$	$r a r$			normal	$\operatorname{\mathbf{NPc}}$
$4_{37}$	$a a a$		$rr\breve{r}$	$a r r$	$r a r$			normal	$\operatorname{\mathbf{NPc}}$
$5_{37}$		$r r r$	$rr\breve{r}$	$a r r$	$r a r$			normal	$\operatorname{\mathbf{P}}$
$6_{37}$	$a a a$	$r r r$	$rr\breve{r}$	$a r r$	$r a r$			normal	$\operatorname{\mathbf{P}}$
$7_{37}$		$r r r$				$r a a$		normal	$\operatorname{\mathbf{NPc}}$
$8_{37}$	$a a a$	$r r r$				$r a a$		normal	$\operatorname{\mathbf{P}}$
$9_{37}$			$rr\breve{r}$			$r a a$		normal	$\operatorname{\mathbf{NPc}}$
$10_{37}$	$a a a$		$rr\breve{r}$			$r a a$		normal	$\operatorname{\mathbf{NPc}}$
$11_{37}$		$r r r$	$rr\breve{r}$			$r a a$		normal	$\operatorname{\mathbf{NPc}}$
$12_{37}$	$a a a$	$r r r$	$rr\breve{r}$			$r a a$		normal	$\operatorname{\mathbf{P}}$
$13_{37}$	$a a a$	$r r r$		$a r r$		$r a a$		f.u.	$\operatorname{\mathbf{P}}\nobreak\ \cite[cite]{[\@@bibref{}{BodirskyKutz}{}{}]}$
$14_{37}$		$r r r$		$a r r$	$r a r$	$r a a$		none	$\operatorname{\mathbf{P}}$
$15_{37}$	$a a a$	$r r r$		$a r r$	$r a r$	$r a a$		normal	$\operatorname{\mathbf{NPc}}\nobreak\ \cite[cite]{[\@@bibref{}{BroxvallJonsson}% {}{}]}$
$16_{37}$		$r r r$	$rr\breve{r}$	$a r r$	$r a r$	$r a a$		none	$\operatorname{\mathbf{P}}$
$17_{37}$	$a a a$	$r r r$	$rr\breve{r}$	$a r r$	$r a r$	$r a a$		$\neg\text{f.u.}$	$\operatorname{\mathbf{P}}$
$18_{37}$							$r r a$	normal	$\operatorname{\mathbf{NPc}}$
$19_{37}$		$r r r$	$rr\breve{r}$				$r r a$	normal	$\operatorname{\mathbf{NPc}}$
$20_{37}$	$a a a$			$a r r$	$r a r$		$r r a$	normal	$\operatorname{\mathbf{NPc}}$
$21_{37}$	$a a a$	$r r r$		$a r r$	$r a r$		$r r a$	none	$\operatorname{\mathbf{P}}$
$22_{37}$	$a a a$	$r r r$	$rr\breve{r}$	$a r r$	$r a r$		$r r a$	normal	$\operatorname{\mathbf{P}}$
$23_{37}$		$r r r$				$r a a$	$r r a$	normal	$\operatorname{\mathbf{NPc}}$
$24_{37}$	$a a a$	$r r r$				$r a a$	$r r a$	none	$\operatorname{\mathbf{P}}$
$25_{37}$		$r r r$	$rr\breve{r}$			$r a a$	$r r a$	none	$\operatorname{\mathbf{P}}$
$26_{37}$	$a a a$	$r r r$	$rr\breve{r}$			$r a a$	$r r a$	none	$\operatorname{\mathbf{P}}$
$27_{37}$		$r r r$		$a r r$		$r a a$	$r r a$	none	$\operatorname{\mathbf{P}}$
$28_{37}$	$a a a$	$r r r$		$a r r$		$r a a$	$r r a$	none	$\operatorname{\mathbf{P}}$
$29_{37}$		$r r r$	$rr\breve{r}$	$a r r$		$r a a$	$r r a$	none	$\operatorname{\mathbf{P}}$
$30_{37}$	$a a a$	$r r r$	$rr\breve{r}$	$a r r$		$r a a$	$r r a$	f.u.	$\operatorname{\mathbf{NPc}}$
$31_{37}$	$a a a$			$a r r$	$r a r$	$r a a$	$r r a$	flex	$\operatorname{\mathbf{NPc}}$
$32_{37}$		$r r r$		$a r r$	$r a r$	$r a a$	$r r a$	none	$\operatorname{\mathbf{P}}$
$33_{37}$	$a a a$	$r r r$		$a r r$	$r a r$	$r a a$	$r r a$	flex	$\operatorname{\mathbf{NPc}}$
$34_{37}$			$rr\breve{r}$	$a r r$	$r a r$	$r a a$	$r r a$	none	$\operatorname{\mathbf{P}}$
$35_{37}$	$a a a$		$rr\breve{r}$	$a r r$	$r a r$	$r a a$	$r r a$	flex	$\operatorname{\mathbf{NPc}}$
$36_{37}$		$r r r$	$rr\breve{r}$	$a r r$	$r a r$	$r a a$	$r r a$	flex	$\operatorname{\mathbf{NPc}}$
$37_{37}$	$a a a$	$r r r$	$rr\breve{r}$	$a r r$	$r a r$	$r a a$	$r r a$	flex	$\operatorname{\mathbf{P}}$

Table 5: The symmetric relation algebras

1_{65}

–

65_{65}

with four atoms

a,b,c,\operatorname{Id}

, representability information, and complexity of their NSP.

$\#_{65}$	$a a a$	$b b b$	$c c c$	$a b b$	$b a a$	$a c c$	$c a a$	$b c c$	$c b b$	$a b c$	Representation	NSP Complexity
$1_{65}$				$a b b$		$a c c$		$b c c$			normal	$\operatorname{\mathbf{NPc}}$
$2_{65}$	$a a a$			$a b b$		$a c c$		$b c c$			normal	$\operatorname{\mathbf{NPc}}$
$3_{65}$		$b b b$		$a b b$		$a c c$		$b c c$			normal	$\operatorname{\mathbf{NPc}}$
$4_{65}$	$a a a$	$b b b$		$a b b$		$a c c$		$b c c$			normal	$\operatorname{\mathbf{NPc}}$
$5_{65}$			$c c c$	$a b b$		$a c c$		$b c c$			normal	$\operatorname{\mathbf{NPc}}$
$6_{65}$	$a a a$		$c c c$	$a b b$		$a c c$		$b c c$			normal	$\operatorname{\mathbf{NPc}}$
$7_{65}$		$b b b$	$c c c$	$a b b$		$a c c$		$b c c$			normal	$\operatorname{\mathbf{P}}$
$8_{65}$	$a a a$	$b b b$	$c c c$	$a b b$		$a c c$		$b c c$			normal	$\operatorname{\mathbf{P}}$
$9_{65}$				$a b b$	$b a a$	$a c c$		$b c c$			$\neg\text{f.u.}$	$\operatorname{\mathbf{NPc}}$
$10_{65}$	$a a a$			$a b b$	$b a a$	$a c c$		$b c c$			normal	$\operatorname{\mathbf{NPc}}$
$11_{65}$	$a a a$	$b b b$		$a b b$	$b a a$	$a c c$		$b c c$			normal	$\operatorname{\mathbf{NPc}}$
$12_{65}$			$c c c$	$a b b$	$b a a$	$a c c$		$b c c$			$\neg\text{f.u.}$	$\operatorname{\mathbf{NPc}}$
$13_{65}$	$a a a$		$c c c$	$a b b$	$b a a$	$a c c$		$b c c$			normal	$\operatorname{\mathbf{NPc}}$
$14_{65}$	$a a a$	$b b b$	$c c c$	$a b b$	$b a a$	$a c c$		$b c c$			normal	$\operatorname{\mathbf{P}}$
$15_{65}$					$b a a$	$a c c$	$c a a$	$b c c$			$\neg\text{f.u.}$	$\operatorname{\mathbf{NPc}}$
$16_{65}$	$a a a$				$b a a$	$a c c$	$c a a$	$b c c$			normal	$\operatorname{\mathbf{NPc}}$
$17_{65}$		$b b b$			$b a a$	$a c c$	$c a a$	$b c c$			$\neg\text{f.u.}$	$\operatorname{\mathbf{NPc}}$
$18_{65}$	$a a a$	$b b b$			$b a a$	$a c c$	$c a a$	$b c c$			normal	$\operatorname{\mathbf{NPc}}$
$19_{65}$	$a a a$		$c c c$		$b a a$	$a c c$	$c a a$	$b c c$			normal	$\operatorname{\mathbf{P}}$
$20_{65}$	$a a a$	$b b b$	$c c c$		$b a a$	$a c c$	$c a a$	$b c c$			normal	$\operatorname{\mathbf{P}}$
$21_{65}$				$a b b$	$b a a$	$a c c$	$c a a$	$b c c$	$c b b$		none	$\operatorname{\mathbf{P}}$
$22_{65}$	$a a a$			$a b b$	$b a a$	$a c c$	$c a a$	$b c c$	$c b b$		none	$\operatorname{\mathbf{P}}$
$23_{65}$	$a a a$	$b b b$		$a b b$	$b a a$	$a c c$	$c a a$	$b c c$	$c b b$		none	$\operatorname{\mathbf{P}}$
$24_{65}$	$a a a$	$b b b$	$c c c$	$a b b$	$b a a$	$a c c$	$c a a$	$b c c$	$c b b$		f.u.	$\operatorname{\mathbf{P}}$
$25_{65}$										$a b c$	normal	$\operatorname{\mathbf{NPc}}$
$26_{65}$	$a a a$			$a b b$						$a b c$	normal	$\operatorname{\mathbf{NPc}}$
$27_{65}$	$a a a$	$b b b$		$a b b$	$b a a$					$a b c$	normal	$\operatorname{\mathbf{NPc}}$
$28_{65}$	$a a a$			$a b b$		$a c c$				$a b c$	normal	$\operatorname{\mathbf{NPc}}$
$29_{65}$	$a a a$	$b b b$	$c c c$		$b a a$		$c a a$			$a b c$	normal	$\operatorname{\mathbf{NPc}}$
$30_{65}$	$a a a$		$c c c$	$a b b$	$b a a$		$c a a$			$a b c$	f.u.	$\operatorname{\mathbf{NPc}}$
$31_{65}$	$a a a$	$b b b$	$c c c$	$a b b$	$b a a$		$c a a$			$a b c$	f.u.	$\operatorname{\mathbf{NPc}}$
$32_{65}$	$a a a$			$a b b$	$b a a$	$a c c$	$c a a$			$a b c$	flex	$\operatorname{\mathbf{NPc}}$
$33_{65}$	$a a a$	$b b b$		$a b b$	$b a a$	$a c c$	$c a a$			$a b c$	flex	$\operatorname{\mathbf{NPc}}$
$34_{65}$	$a a a$	$b b b$	$c c c$	$a b b$	$b a a$	$a c c$	$c a a$			$a b c$	flex	$\operatorname{\mathbf{NPc}}$
$35_{65}$	$a a a$	$b b b$		$a b b$		$a c c$		$b c c$		$a b c$	none	$\operatorname{\mathbf{P}}$
$36_{65}$	$a a a$	$b b b$	$c c c$	$a b b$		$a c c$		$b c c$		$a b c$	none	$\operatorname{\mathbf{P}}$
$37_{65}$	$a a a$	$b b b$		$a b b$	$b a a$	$a c c$		$b c c$		$a b c$	none	$\operatorname{\mathbf{P}}$
$38_{65}$	$a a a$	$b b b$	$c c c$	$a b b$	$b a a$	$a c c$		$b c c$		$a b c$	none	$\operatorname{\mathbf{P}}$
$39_{65}$				$a b b$			$c a a$	$b c c$		$a b c$	$\neg\text{f.u.}$	$\operatorname{\mathbf{NPc}}$
$40_{65}$	$a a a$			$a b b$			$c a a$	$b c c$		$a b c$	none	$\operatorname{\mathbf{P}}$
$41_{65}$	$a a a$	$b b b$		$a b b$			$c a a$	$b c c$		$a b c$	none	$\operatorname{\mathbf{P}}$
$42_{65}$	$a a a$	$b b b$	$c c c$	$a b b$			$c a a$	$b c c$		$a b c$	none	$\operatorname{\mathbf{P}}$
$43_{65}$				$a b b$	$b a a$		$c a a$	$b c c$		$a b c$	none	$\operatorname{\mathbf{P}}$
$44_{65}$	$a a a$			$a b b$	$b a a$		$c a a$	$b c c$		$a b c$	none	$\operatorname{\mathbf{P}}$
$45_{65}$		$b b b$		$a b b$	$b a a$		$c a a$	$b c c$		$a b c$	none	$\operatorname{\mathbf{P}}$
$46_{65}$	$a a a$	$b b b$		$a b b$	$b a a$		$c a a$	$b c c$		$a b c$	normal	$\operatorname{\mathbf{NPc}}$
$47_{65}$			$c c c$	$a b b$	$b a a$		$c a a$	$b c c$		$a b c$	none	$\operatorname{\mathbf{P}}$
$48_{65}$	$a a a$		$c c c$	$a b b$	$b a a$		$c a a$	$b c c$		$a b c$	none	$\operatorname{\mathbf{P}}$
$49_{65}$		$b b b$	$c c c$	$a b b$	$b a a$		$c a a$	$b c c$		$a b c$	none	$\operatorname{\mathbf{P}}$
$50_{65}$	$a a a$	$b b b$	$c c c$	$a b b$	$b a a$		$c a a$	$b c c$		$a b c$	none	$\operatorname{\mathbf{P}}$

51_{65}

b b b

b a a

a c c

c a a

b c c

a b c

\neg\text{f.u.}

\operatorname{\mathbf{NPc}}

52_{65}

a a a

b b b

b a a

a c c

c a a

b c c

a b c

normal

\operatorname{\mathbf{NPc}}

53_{65}

a a a

b b b

c c c

b a a

a c c

c a a

b c c

a b c

normal

\operatorname{\mathbf{P}}

54_{65}

a b b

b a a

a c c

c a a

b c c

a b c

none

\operatorname{\mathbf{P}}

55_{65}

a a a

a b b

b a a

a c c

c a a

b c c

a b c

flex

\operatorname{\mathbf{NPc}}

56_{65}

b b b

a b b

b a a

a c c

c a a

b c c

a b c

\neg\text{f.u.}

\operatorname{\mathbf{NPc}}

[8]

57_{65}

a a a

b b b

a b b

b a a

a c c

c a a

b c c

a b c

flex

\operatorname{\mathbf{NPc}}

58_{65}

c c c

a b b

b a a

a c c

c a a

b c c

a b c

none

\operatorname{\mathbf{P}}

59_{65}

a a a

c c c

a b b

b a a

a c c

c a a

b c c

a b c

flex

\operatorname{\mathbf{NPc}}

60_{65}

b b b

c c c

a b b

b a a

a c c

c a a

b c c

a b c

none

\operatorname{\mathbf{P}}

61_{65}

a a a

b b b

c c c

a b b

b a a

a c c

c a a

b c c

a b c

flex

\operatorname{\mathbf{P}}

62_{65}

a b b

b a a

a c c

c a a

b c c

c b b

a b c

\neg\text{f.u.}

\operatorname{\mathbf{NPc}}

63_{65}

a a a

a b b

b a a

a c c

c a a

b c c

c b b

a b c

flex

\operatorname{\mathbf{NPc}}

64_{65}

a a a

b b b

a b b

b a a

a c c

c a a

b c c

c b b

a b c

flex

\operatorname{\mathbf{NPc}}

65_{65}

a a a

b b b

c c c

a b b

b a a

a c c

c a a

b c c

c b b

a b c

flex

\operatorname{\mathbf{P}}\phantom{XXXXXXXl}

[bib.bib1] [1] Hajnal Andréka and Roger D. Maddux. Representations for small relation algebras. Notre Dame Journal of Formal Logic, 35(4):550–562, 1994. doi:10.1305/NDJFL/1040408612.

[bib.bib2] [2] Jørgen Bang-Jensen and Jing Huang. Quasi-transitive digraphs. Journal of Graph Theory, 20(2):141–161, 1995. doi:10.1002/jgt.3190200205.

[bib.bib3] [3] Libor Barto, Michael Kompatscher, Miroslav Olšák, Trung Van Pham, and Michael Pinsker. The equivalence of two dichotomy conjectures for infinite domain constraint satisfaction problems. In Proceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science – LICS’17, 2017. Preprint arXiv:1612.07551. arXiv:1612.07551.

[bib.bib4] [4] Libor Barto, Jakub Opršal, and Michael Pinsker. The wonderland of reflections. Israel Journal of Mathematics, 223(1):363–398, 2018.

[bib.bib5] [5] Libor Barto and Michael Pinsker. The algebraic dichotomy conjecture for infinite domain constraint satisfaction problems. In Proceedings of the 31st Annual IEEE Symposium on Logic in Computer Science – LICS’16, pages 615–622, 2016. Preprint arXiv:1602.04353. arXiv:1602.04353.

[bib.bib6] [6] 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. doi:10.1007/978-3-030-02149-8_1.

[bib.bib7] [7] Manuel Bodirsky. Complexity of Infinite-Domain Constraint Satisfaction. Lecture Notes in Logic (52). Cambridge University Press, Cambridge, United Kingdom; New York, NY, 2021. doi:10.1017/9781107337534.

[bib.bib8] [8] Manuel Bodirsky, Santiago Guzmán-Pro, Moritz Jahn, Matěj Konečný, and Paul Winkler. Circular chromatic numbers, balanceability, relation algebras, and network satisfaction problems, 2025. Preprint available under https://arxiv.org/abs/2512.06878. doi:10.48550/arXiv.2512.06878.

[bib.bib9] [9] Manuel Bodirsky and Jan Kára. The complexity of temporal constraint satisfaction problems. Journal of the ACM, 57(2):1–41, 2009. An extended abstract appeared in the Proceedings of the Symposium on Theory of Computing (STOC). doi:10.1145/1667053.1667058.

[bib.bib10] [10] 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. doi:10.1007/978-3-030-43520-2_3.

[bib.bib11] [11] 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, 2022. doi:10.1613/jair.1.14195.

[bib.bib12] [12] Manuel Bodirsky and Simon Knäuer. Network satisfaction problems solved by $k$ -consistency. In 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023, July 10-14, 2023, Paderborn, Germany, pages 116:1–116:20, 2023. doi:10.4230/LIPIcs.ICALP.2023.116.

[bib.bib13] [13] Manuel Bodirsky and Martin Kutz. Pure dominance constraints. In Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS), pages 287–298, 2002. doi:10.1007/3-540-45841-7_23.

[bib.bib14] [14] Manuel Bodirsky, Barnaby Martin, Michael Pinsker, and András Pongrácz. Constraint satisfaction problems for reducts of homogeneous graphs. SIAM Journal on Computing, 48(4):1224–1264, 2019. A conference version appeared in the Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, pages 119:1-119:14. doi:10.1137/16M1082974.

[bib.bib15] [15] Manuel Bodirsky and Michael Pinsker. Schaefer’s theorem for graphs. Journal of the ACM, 62(3):52 pages (article number 19), 2015. A conference version appeared in the Proceedings of STOC 2011, pages 655-664. doi:10.1145/2764899.

[bib.bib16] [16] Manuel Bodirsky, Michael Pinsker, and András Pongrácz. Projective clone homomorphisms. Journal of Symbolic Logic, 86(1):148–161, 2021. doi:10.1017/JSL.2019.23.

[bib.bib17] [17] Mathias Broxvall and Peter Jonsson. Point algebras for temporal reasoning: Algorithms and complexity. Artificial Intelligence, 149(2):179–220, 2003. doi:10.1016/S0004-3702(03)00075-4.

[bib.bib18] [18] 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. doi:10.1109/FOCS.2017.37.

[bib.bib19] [19] Jakub Bulín, Andrei A. Krokhin, and Jakub Opršal. Algebraic approach to promise constraint satisfaction. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 602–613, 2019. doi:10.1145/3313276.3316300.

[bib.bib20] [20] Stanley N. Burris and Hanamantagouda P. Sankappanavar. A Course in Universal Algebra. Springer Verlag, Berlin, 1981.

[bib.bib21] [21] Peter J. Cameron. The random graph. R. L. Graham and J. Nešetřil, Editors, The Mathematics of Paul Erdös, 1996.

[bib.bib22] [22] Gregory Cherlin. Homogeneous ordered graphs and metrically homogeneous graphs, 2020. Preprint.

[bib.bib23] [23] Gregory L. Cherlin. The classification of countable homogeneous directed graphs and countable homogeneous $n$ -tournaments. AMS Memoir, 131(621), January 1998.

[bib.bib24] [24] Stephen D. Comer. Extension of polygroups by polygroups and their representations using color schemes. In Ralph S. Freese and Octavio C. Garcia, editors, Universal Algebra and Lattice Theory, pages 91–103, Berlin, Heidelberg, 1983. Springer Berlin Heidelberg.

[bib.bib25] [25] Stephen D. Comer. A remark on chromatic polygroups. Congressus Numerantium, 38:85–95, 1983.

[bib.bib26] [26] Matteo Cristiani and Robin Hirsch. The complexity of the constraint satisfaction problem for small relation algebras. Artificial Intelligence Journal, 156:177–196, 2004. doi:10.1016/J.ARTINT.2004.02.003.

[bib.bib27] [27] Michael Garey and David Johnson. A guide to NP-completeness. CSLI Press, Stanford, 1978.

[bib.bib28] [28] C. Ward Henson. Countable homogeneous relational systems and categorical theories. Journal of Symbolic Logic, 37:494–500, 1972.

[bib.bib29] [29] R. Hirsch and I. Hodkinson. Representability is not decidable for finite relation algebras. Transactions of the American Mathematical Society, 353(4):1387–1401, 2001.

[bib.bib30] [30] Robin Hirsch. Relation algebras of intervals. Artificial Intelligence Journal, 83:1–29, 1996.

[bib.bib31] [31] Robin Hirsch. A finite relation algebra with undecidable network satisfaction problem. Logic Journal of the IGPL, 7(4):547–554, 1999. doi:10.1093/JIGPAL/7.4.547.

[bib.bib32] [32] Wilfrid Hodges. A shorter model theory. Cambridge University Press, Cambridge, 1997.

[bib.bib33] [33] Alistair H. Lachlan and Robert E. Woodrow. Countable ultrahomogeneous undirected graphs. Transactions of the AMS, 262(1):51–94, 1980.

[bib.bib34] [34] Richard E. Ladner. On the structure of polynomial time reducibility. Journal of the ACM, 22(1):155–171, 1975. doi:10.1145/321864.321877.

[bib.bib35] [35] R. Lyndon. The representation of relational algebras. Annals of Mathematics, 51(3):707–729, 1950.

[bib.bib36] [36] Roger D. Maddux. Finite symmetric integral relation algebras with no 3-cycles. In Renate A. Schmidt, editor, Relations and Kleene Algebra in Computer Science, 9th International Conference on Relational Methods in Computer Science and 4th International Workshop on Applications of Kleene Algebra, RelMiCS/AKA 2006, Manchester, UK, August 29-September 2, 2006, Proceedings, volume 4136 of Lecture Notes in Computer Science, pages 2–29. Springer, 2006. doi:10.1007/11828563_2.

[bib.bib37] [37] Roger Duncan Maddux. Relation Algebras: Volume 150. Studies in logic and the foundations of mathematics. Elsevier Science, London, England, May 2006.

[bib.bib38] [38] Donald Monk. On representable relation algebras. Michigan Mathematical Journal, 11(3):207–210, 1964. doi:10.1307/mmj/1028999131.

[bib.bib39] [39] Alfred Tarski. On the calculus of relations. J. Symbolic Logic, 6, 1941. doi:10.2307/2268577.

[bib.bib40] [40] Alfred Tarski. Contributions to the theory of models. Koninklijke Nederlandse Akademie van Wetenschappen, Proceedings, 58:56–64, 1955.

[bib.bib41] [41] Marc Vilain, Henry Kautz, and Peter van Beek. Constraint propagation algorithms for temporal reasoning: A revised report. Reading in Qualitative Reasoning about Physical Systems, pages 373–381, 1989.

[bib.bib42] [42] Dmitriy Zhuk. A proof of the CSP dichotomy conjecture. J. ACM, 67(5):30:1–30:78, 2020. doi:10.1145/3402029.

[bib.bib43] [43] 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. arXiv:1704.01914.

[bib.bib44] [44] Paul-Hermann Zieschang. Hypergroups. Springer, 2023.

The Network Satisfaction Problem for Relation Algebras with at Most 4 Atoms

Abstract

Keywords and phrases:

Category:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Supplementary Material:

Funding:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Example 1.

1.1 Network Satisfaction Problems and CSP Complexity

Example 2.

Conjecture 2.

1.2 Contributions

Theorem 3.

Theorem 4.

1.3 Significance for Constraint Satisfaction

2 Preliminaries

2.1 Constraint Satisfaction

Example 5.

Definition 6.

Proposition 7 (see, e.g., [7, Theorem 3.1.4]).

Definition 8.

2.2 Relation Algebras

Definition 9.

Definition 10.

Definition 11.

Definition 12.

Definition 13.

Definition 14.

Definition 15.

Definition 16.

Definition 17 (The Amalgamation Property).

Theorem 18 ([6, Theorem 8]).

Theorem 19.

3 Representations for Algebras with at most 4 Atoms

Lemma 20 (see, e.g., [12]).

Example 21.

Proposition 22.

Theorem 23.

Definition 24.

Theorem 25 ([36, Theorem 5], see also [24]).

Lemma 26.

Theorem 27.

Theorem 28.

4 NP-hard Algebras with at most 4 Atoms

Lemma 29.

Proposition 30 ([11, Theorem 2.21 and Proposition 6.1]).

Proposition 31 ([12, Lemma 4.3]).

Theorem 32 ([11, Theorem 9.1]).

Theorem 33 ([10, Theorem 23]).

Theorem 34 ([10, Theorem 29]).

Lemma 35.

Lemma 36.

Proposition 37.

Proposition 38.

▶ Remark 39.

5 Tractable Algebras with at most 4 Atoms

Proposition 40 ([12, Proposition 2.16]).

Lemma 41.

5.1 The Relation Algebra 𝟐𝟒𝟔𝟓

Lemma 42.

Lemma 43.

Definition 44.

Definition 45.

Lemma 46.

Proof.

Proposition 47.

Proof.

6 Open Problems

Question 47.

Question 47.

Problem 47.

Problem 47.

References

$\blacktriangleright$ Remark 39.

5.1 The Relation Algebra ${24_{65}}$