---
abstract: '> A natural and established way to restrict the constraint satisfaction problem is to fix the relations that can be used to pose constraints; such a family of relations is called a *constraint language*. In this article, we study arc consistency, a heavily investigated inference method, and three extensions thereof from the perspective of constraint languages. We conduct a comparison of the studied methods on the basis of which constraint languages they solve, and we present new polynomial-time tractability results for singleton arc consistency, the most powerful method studied.'
author:
- 'Hubie Chen[^1], Victor Dalmau[^2], Berit Grußien[^3]'
bibliography:
- 'local.bib'
title: Arc Consistency and Friends
---

\[theorem\] [Lemma]{} \[theorem\] [Remark]{} \[theorem\] [Fact]{} \[theorem\] [Claim]{} \[theorem\] [Corollary]{} \[theorem\] [Definition]{} \[theorem\] [Proposition]{} \[theorem\] [Warning]{} \[theorem\] [Example]{}

Introduction
============

Background
----------

The constraint satisfaction problem (CSP) involves deciding, given a set of variables and a set of constraints on the variables, whether or not there is an assignment to the variables satisfying all of the constraints. Cases of the constraint satisfaction problem appear in many fields of study, including artificial intelligence, spatial and temporal reasoning, logic, combinatorics, and algebra. Indeed, the constraint satisfaction problem is flexible in that it admits a number of equivalent formulations. In this paper, we work with the formulation as the relational homomorphism problem: given two similar relational structures ${\mathbf{A}}$ and ${\mathbf{B}}$, does there exist a homomorphism from ${\mathbf{A}}$ to ${\mathbf{B}}$? In this formulation, one can view each relation of ${\mathbf{A}}$ as containing variable tuples that are constrained together, and the corresponding relation of ${\mathbf{B}}$ as containing the permissible values for the variable tuples [@FederVardi].

The constraint satisfaction problem is in general NP-hard; this general intractability has motivated the study of restricted versions of the CSP that have various desirable complexity and algorithmic properties. A natural and well-studied way to restrict the CSP is to fix the value relations that can be used to pose constraints; in the homomorphism formulation, this corresponds to fixing the right-hand side structure ${\mathbf{B}}$, which is also known as the *constraint language*. Each structure ${\mathbf{B}}$ then gives rise to a problem ${{\mathsf{CSP}}}({\mathbf{B}})$, and one obtains a rich family of problems that include boolean satisfiability problems, graph homomorphism problems, and satisfiability problems on algebraic equations. One of the primary current research threads involving such problems is to understand for which finite-universe constraint languages ${\mathbf{B}}$ the problem ${{\mathsf{CSP}}}({\mathbf{B}})$ is polynomial-time tractable [@bulatov-valeriote]; there is also work on characterizing the languages ${\mathbf{B}}$ for which the problem ${{\mathsf{CSP}}}({\mathbf{B}})$ is contained in lower complexity classes such as L (logarithmic space) and NL (non-deterministic logarithmic space) [@dalmau-pathwidth; @larose-tesson]. With such aims providing motivation, there have been efforts to characterize the languages amenable to solution by certain algorithmic techniques, notably, representing solution spaces by generating sets [@IMMVW] and consistency methods [@LaroseZadori; @abd-affine; @bkbw], which we now turn to discuss.

Checking for *consistency* is a primary reasoning technique for the practical solution of the CSP, and has been studied theoretically from many viewpoints [@LaroseZadori; @abd-affine; @akv; @abd; @aft; @bkbw; @atserias-weyer]. The most basic and simplest form of consistency is *arc consistency*, which algorithmically involves performing inferences concerning the set of feasible values for each variable. The question of how to efficiently implement an arc consistency check has been studied intensely, and highly optimized implementations that are linear in both time and space have been presented. In general, a consistency check typically involves running an efficient method that performs inference on bounded-size sets of variables, and which can sometimes detect that a CSP instance is inconsistent and has no solution. While these methods exhibit one-sided error in that they do not catch all non-soluble CSP instances (as one expects from the conjunction of their efficiency and the intractability of the CSP), it has been shown that, for certain constraint languages, they can serve as complete decision procedures, by which is meant, they detect an inconsistency if (and only if) an instance has no solution. As an example, *unit propagation*, a consistency method that can be viewed as arc consistency specialized to SAT formulas, is well-known to decide the Horn-SAT problem in this sense.

Contributions
-------------

In this paper, we study arc consistency and three natural extensions thereof from the perspective of constraint languages. The extensions of AC that we study are look-ahead arc consistency (LAAC) [@SLAAC]; peek arc consistency (PAC) [@peek], and singleton arc consistency (SAC) [@db-sac; @bd-theoretical]. Each of these algorithms is natural, conceptually simple, readily understandable, and easily implementable using arc consistency as a black box. Tractability results for constraint languages have been presented for AC by Feder and Vardi [@FederVardi] (for instance); and for LAAC and PAC in the previously cited work. In fact, for each of these three algorithms, characterizations of the class of tractable languages have been given, as we discuss in the paper.

We give a uniform presentation of these algorithms (Section \[sect:algorithms\]), and conduct a comparison of these algorithms on the basis of which languages they solve (Section \[sect:comparison\]). Our comparison shows, roughly, that the algorithms can be placed into a hierarchy: solvability of a language by AC or LAAC implies solvability by PAC; solvability by PAC in turn implies solvability by SAC (see Section \[sect:comparison\] for precise statements). We also study the strictness of the containments shown. We thus contribute to a basic, foundational understanding of the scope of these algorithms and of the situations in which these algorithms can be demonstrated to be effective.

We then present new tractability results for singleton arc consistency (Section \[sect:tractability\]). We prove that languages having certain types of *2-semilattice polymorphisms* can be solved by singleton arc consistency; and, we prove that any language having a *majority polymorphism* is solvable by singleton arc consistency. The presence of a majority polymorphism is a robust and well-studied condition: majority polymorphisms were used to give some of the initial language tractability results, are known to exactly characterize the languages such that *3-consistency* implies *global consistency* (we refer to [@CCC] for definitions and more details), and gave one of the first large classes of languages whose constraint satisfaction problem could be placed in non-deterministic logarithmic space [@majority-nl]. While the languages that we study are already known to be polynomial-time tractable [@CCC; @twosemilattices], from the standpoint of understanding the complexity and algorithmic properties of constraint languages, we believe our tractability results to be particularly attractive for a couple of reasons. First, relative to a fixed language, singleton arc consistency runs in quadratic time [@bd-theoretical], constituting a highly non-trivial running time improvement over the cubic time bound that was previously known for the studied languages. Also, in showing that these languages are amenable to solution by singleton arc consistency, we demonstrate their polynomial-time tractability in an alternative fashion via an algorithm that is different from the previously used ones; the techniques that we employ expose a different type of structure in the studied constraint languages.

Preliminaries
=============

Our definitions and notation are fairly standard. For an integer $k \geq 1$, we use the notation $[k]$ to denote the set containing the first $k$ positive integers, that is, the set $\{ 1, \ldots, k \}$.

#### Structures.

A *tuple* over a set $B$ is an element of $B^k$ for a value $k \geq 1$ called the *arity* of the tuple; when ${\overline{t}}$ is a tuple, we often use the notation ${\overline{t}} = (t_1, \ldots, t_k)$ to denote its entries. A *relation* over a set $B$ is a subset of $B^k$ for a value $k \geq 1$ called the *arity* of the relation. We use $\pi_i$ to denote the operator that projects onto the $i$th coordinate: $\pi_i({\overline{t}})$ denotes the $i$th entry $t_i$ of a tuple ${\overline{t}} = (t_1, \ldots, t_k)$, and for a relation $R$ we define $\pi_i(R) = \{ \pi_i({\overline{t}}) ~|~ {\overline{t}} \in R \}$. Similarly, for a subset $I \subseteq [k]$ whose elements are $i_1 < \cdots < i_m$, we use $\pi_I({\overline{t}})$ to denote the tuple $(t_{i_1}, \ldots, t_{i_m})$, and we define $\pi_I(R) = \{ \pi_I({\overline{t}}) ~|~ {\overline{t}} \in R \}$.

A *signature* $\sigma$ is a set of symbols, each of which has an associated arity. A *structure* ${\mathbf{B}}$ over signature $\sigma$ consists of a universe $B$, which is a set, and a relation $R^{{\mathbf{B}}} \subseteq B^k$ for each symbol $R \in \sigma$ of arity $k$. (Note that in this paper, we are concerned only with relational structures, which we refer to simply as structures.) Throughout, we will use the bold capital letters ${\mathbf{A}}, {\mathbf{B}}, \ldots$ to denote structures, and the corresponding non-bold capital letters $A, B, \ldots$ to denote their universes. We say that a structure ${\mathbf{B}}$ is *finite* if its universe $B$ has finite size. Unless stated otherwise, we assume all structures under discussion in this paper to be finite. We say that a structure ${\mathbf{B}}$ *has all constants* if for each $b \in B$, there is a relation symbol $R_b$ with $R_b^{{\mathbf{B}}} = \{ (b) \}$.

When two structures ${\mathbf{A}}$ and ${\mathbf{B}}$ are defined over the same signature $\sigma$, we say that they are *similar*. We define the following notions on similar structures. For similar structures ${\mathbf{A}}$ and ${\mathbf{B}}$ over a signature $\sigma$, we say that ${\mathbf{A}}$ is an *induced substructure* of ${\mathbf{B}}$ if $A \subseteq B$ and for every $R \in \sigma$ of arity $k$, it holds that $R^{{\mathbf{A}}} = A^k \cap R^{{\mathbf{B}}}$. Observe that for a structure ${\mathbf{B}}$ and a subset $B' \subseteq B$, there is exactly one induced substructure of ${\mathbf{B}}$ with universe $B'$. For similar structures ${\mathbf{A}}$ and ${\mathbf{B}}$ over a signature $\sigma$, the product structure ${\mathbf{A}}\times {\mathbf{B}}$ is defined to be the structure with universe $A \times B$ and such that $R^{{\mathbf{A}}\times {\mathbf{B}}} = 
\{ ((a_1, b_1), \ldots, (a_k, b_k)) ~|~ {\overline{a}} \in R^{{\mathbf{A}}}, {\overline{b}} \in R^{{\mathbf{B}}} \}$ for all $R \in \sigma$. We use ${\mathbf{A}}^n$ to denote the $n$-fold product ${\mathbf{A}}\times \cdots \times {\mathbf{A}}$.

We say that a structure ${\mathbf{B}}$ over signature $\sigma'$ is an *expansion* of another structure ${\mathbf{A}}$ over signature $\sigma$ if (1) $\sigma' \supseteq \sigma$, (2) the universe of ${\mathbf{B}}$ is equal to the universe of ${\mathbf{A}}$, and (3) for every symbol $R \in \sigma$, it holds that $R^{{\mathbf{B}}} = R^{{\mathbf{A}}}$. We will use the following non-standard notation. For any structure ${\mathbf{A}}$ (over signature $\sigma$) and any subset $S \subseteq A$, we define $[{\mathbf{A}}, S]$ to be the expansion of ${\mathbf{A}}$ with the signature $\sigma \cup \{ U \}$ where $U$ is a new symbol of arity $1$, defined by $U^{[{\mathbf{A}}, S]} = S$ and $R^{[{\mathbf{A}}, S]} = R^{{\mathbf{A}}}$ for all $R \in \sigma$. More generally, for a structure ${\mathbf{A}}$ (over $\sigma$) and a sequence of subsets $S_1, \ldots, S_n \subseteq A$, we define $[{\mathbf{A}}, S_1, \ldots, S_n]$ to be the expansion of ${\mathbf{A}}$ with the signature $\sigma \cup \{ U_1, \ldots, U_n \}$ where $U_1, \ldots, U_n$ are new symbols of arity $1$, defined by $U_i^{[{\mathbf{A}}, S_1, \ldots, S_n]} = S_i$ for all $i \in [n]$, and $R^{[{\mathbf{A}}, S_1, \ldots, S_n]} = R^{{\mathbf{A}}}$ for all $R \in \sigma$.

#### Homomorphisms and the constraint satisfaction problem.

For similar structures ${\mathbf{A}}$ and ${\mathbf{B}}$ over the signature $\sigma$, a *homomorphism* from ${\mathbf{A}}$ to ${\mathbf{B}}$ is a mapping $h: A \rightarrow B$ such that for every symbol $R$ of $\sigma$ and every tuple $(a_1, \ldots, a_k) \in R^{{\mathbf{A}}}$, it holds that $(h(a_1), \ldots, h(a_k)) \in R^{{\mathbf{B}}}$. We use ${\mathbf{A}}{\rightarrow}{\mathbf{B}}$ to indicate that there is a homomorphism from ${\mathbf{A}}$ to ${\mathbf{B}}$; when this holds, we also say that ${\mathbf{A}}$ *is homomorphic to* ${\mathbf{B}}$. It is well-known and straightforward to verify that the homomorphism relation ${\rightarrow}$ is transitive, that is, if ${\mathbf{A}}{\rightarrow}{\mathbf{B}}$ and ${\mathbf{B}}{\rightarrow}{\mathbf{C}}$, then ${\mathbf{A}}{\rightarrow}{\mathbf{C}}$.

The *constraint satisfaction problem (CSP)* is the problem of deciding, given as input a pair $({\mathbf{A}}, {\mathbf{B}})$ of similar structures, whether or not there exists a homomorphism from ${\mathbf{A}}$ to ${\mathbf{B}}$. When $({\mathbf{A}}, {\mathbf{B}})$ is an instance of the CSP, we will also call a homomorphism from ${\mathbf{A}}$ to ${\mathbf{B}}$ a *satisfying assignment*; say that the instance is *satisfiable* if there exists such a homomorphism; and, say that the instance is *unsatisfiable* if there does not exist such a homomorphism. We generally assume that in an instance of the CSP, the left-hand side structure ${\mathbf{A}}$ contains finitely many tuples. For any structure ${\mathbf{B}}$ (over $\sigma$), the *constraint satisfaction problem for ${\mathbf{B}}$*, denoted by ${{\mathsf{CSP}}}({\mathbf{B}})$, is the constraint satisfaction problem where the right-hand side structure is fixed to be ${\mathbf{B}}$, that is, the problem of deciding, given as input a structure ${\mathbf{A}}$ over $\sigma$, whether or not there exists a homomorphism from ${\mathbf{A}}$ to ${\mathbf{B}}$. In discussing a problem of the form ${{\mathsf{CSP}}}({\mathbf{B}})$, the structure ${\mathbf{B}}$ is often referred to as the *template* or *constraint language*. There are several equivalent definitions of the constraint satisfaction problem. For instance, in logic, the constraint satisfaction problem can be formulated as the model checking problem for primitive positive sentences over relational structures, and in database theory, it can be formulated as the containment problem for conjunctive queries [@ChandraMerlin].

#### Polymorphisms.

When $f: B^n \rightarrow B$ is an operation on $B$ and $${\overline{t_1}} = (t_{11}, \ldots, t_{1k}), \ldots, {\overline{t_n}} = (t_{n1}, \ldots, t_{nk}) \in B^k$$ are tuples of the same arity $k$ over $B$, we use $f({\overline{t_1}}, \ldots, {\overline{t_n}})$ to denote the arity $k$ tuple obtained by applying $f$ coordinatewise, that is, $$f({\overline{t_1}}, \ldots, {\overline{t_n}}) = 
(f(t_{11}, \ldots, t_{n1}), \ldots, f(t_{1k}, \ldots, t_{nk})).$$ An operation $f: B^n \rightarrow B$ is a *polymorphism* of a structure ${\mathbf{B}}$ over $\sigma$ if for every symbol $R \in \sigma$ and any tuples ${\overline{t_1}}, \ldots, {\overline{t_n}} \in R^{{\mathbf{B}}}$, it holds that $f({\overline{t_1}}, \ldots, {\overline{t_n}}) \in R^{{\mathbf{B}}}$. That is, each relation $R^{{\mathbf{B}}}$ is closed under the action of $f$. Equivalently, an operation $f: B^n \rightarrow B$ is a polymorphism of ${\mathbf{B}}$ if it is a homomorphism from ${\mathbf{B}}^n$ to ${\mathbf{B}}$.

Algorithms {#sect:algorithms}
==========

In this section, we give a uniform presentation of the four algorithms under investigation in this paper: arc consistency, look-ahead arc consistency, peek arc consistency, and singleton arc consistency, presented in Sections \[ss:ac\], \[ss:laac\], \[ss:pac\], and \[ss:sac\], respectively. The results on the first three algorithms come from previous work, as we discuss in presenting each of these algorithms; for singleton arc consistency, we here develop results similar to those given for the other algorithms.

Our treatment of arc consistency, peek arc consistency, and singleton arc consistency is uniform: for each of these algorithms, we present a homomorphism-based consistency condition, we show that the algorithm checks precisely this consistency condition, and we give an algebraic condition describing the structures ${\mathbf{B}}$ such that the algorithm solves ${{\mathsf{CSP}}}({\mathbf{B}})$. These three algorithms give one-sided consistency checks: each either correctly rejects an instance as unsatisfiable or outputs “?”, which can be interpreted as a report that it is unknown whether or not the instance is satisfiable. The other algorithm, look-ahead arc consistency, has a somewhat different character. It attempts to build a satisfying assignment one variable at a time, using arc consistency as a filtering criterion; it either returns a satisfying assignment, or outputs “?”.

Throughout this section and in later sections, we will make use of a structure ${\wp}({\mathbf{B}})$ that is defined for every structure ${\mathbf{B}}$, as follows [@FederVardi; @DalmauPearson]. For a structure ${\mathbf{B}}$ (over $\sigma$), we define ${\wp}({\mathbf{B}})$ to be the structure with universe ${\wp}(B) \setminus \{ \emptyset \}$ and where, for every symbol $R \in \sigma$ of arity $k$, $R^{{\wp}({\mathbf{B}})} = \{ (\pi_1 S, \ldots, \pi_k S) ~|~ S \subseteq R^{{\mathbf{B}}}, S \neq \emptyset \}$. Here, ${\wp}(B)$ denotes the power set of the set $B$.

Arc Consistency {#ss:ac}
---------------

We now present the arc consistency algorithm. The main idea of the algorithm is to associate to each element $a \in A$ a set $S_a$ of values which, throughout the execution of the algorithm, has the property that for any solution $h$, it must hold that $h(a) \in S_a$. The algorithm continually shrinks the sets $S_a$ in a natural fashion until they stabilize; at this point, if some set $S_a$ is the empty set, then no solution can exist, and the algorithm rejects the instance.

[**Arc Consistency**]{}\

------------------------------------------------------------------------

Feder and Vardi [@FederVardi] have studied arc consistency, under an equivalent formulation in terms of Datalog Programs, for constraint languages. The results in this section are due to this reference. The connection of the results in Feder and Vardi with arc consistency was made explicit in Dalmau and Pearson [@DalmauPearson].

\[def:acc\] An instance $({\mathbf{A}}, {\mathbf{B}})$ has the *arc consistency condition (ACC)* if there exists a homomorphism from ${\mathbf{A}}$ to ${\wp}({\mathbf{B}})$.

\[prop:acc\] The arc consistency algorithm does not reject an instance $({\mathbf{A}}, {\mathbf{B}})$ if and only if the instance has the ACC.

\[def:ac-solves\] Let ${\mathbf{B}}$ be a structure. We say that arc consistency *solves* ${{\mathsf{CSP}}}({\mathbf{B}})$ if for all structures ${\mathbf{A}}$, the following holds: $({\mathbf{A}}, {\mathbf{B}})$ has the ACC implies that there is a homomorphism ${\mathbf{A}}\rightarrow {\mathbf{B}}$.

Note that the converse of the condition given in this definition always holds: if $h$ is a homomorphism from ${\mathbf{A}}$ to ${\mathbf{B}}$, then the mapping sending each $a \in A$ to the set $\{ h(a) \}$ is a homomorphism from ${\mathbf{A}}$ to ${\wp}({\mathbf{B}})$.

\[thm:ac-solves\] Let ${\mathbf{B}}$ be a structure. Arc consistency solves ${{\mathsf{CSP}}}({\mathbf{B}})$ if and only if there is a homomorphism ${\wp}({\mathbf{B}}) \rightarrow {\mathbf{B}}$.

Look-Ahead Arc Consistency {#ss:laac}
--------------------------

We now present the look-ahead arc consistency algorithm. It attempts to construct a satisfying assignment by setting one variable at a time, using arc consistency as a filter to find a suitable value for each variable.

[ **Look-Ahead Arc Consistency**]{}\

------------------------------------------------------------------------

Look-ahead arc consistency was introduced and studied by Chen and Dalmau [@SLAAC], and the theorem that follows is due to them. This algorithm can be viewed as a generalization of an algorithm for SAT studied by Del Val [@delval].

\[def:laac-solves\] Let ${\mathbf{B}}$ be a structure. We say that look-ahead arc consistency *solves* ${{\mathsf{CSP}}}({\mathbf{B}})$ if for all structures ${\mathbf{A}}$, the following holds: if there exists a homomorphism ${\mathbf{A}}\rightarrow {\mathbf{B}}$, then the look-ahead arc consistency algorithm, given $({\mathbf{A}}, {\mathbf{B}})$, outputs such a homomorphism.

\[thm:laac-solves\] Let ${\mathbf{B}}$ be a structure. Look-ahead arc consistency solves ${{\mathsf{CSP}}}({\mathbf{B}})$ if and only if there is a homomorphism $l: {\wp}({\mathbf{B}}) \times {\mathbf{B}}\rightarrow {\mathbf{B}}$ such that $l( \{ b \}, b') = b$ for all $b, b' \in B$.

Peek Arc Consistency {#ss:pac}
--------------------

We now present the peek arc consistency algorithm. It attempts to find, for each variable $a \in A$, a value $b \in B$ such that when $a$ is set to $b$, the arc consistency check is passed.

[**Peek Arc Consistency**]{}\

------------------------------------------------------------------------

Peek arc consistency was introduced and studied by Bodirsky and Chen [@peek]; the notions and results that follow come from them. In their work, the algorithm is shown to solve certain constraint languages, including some languages having infinite-size universes; such languages actually gave the motivation for introducing the algorithm. In this work, it is pointed out that peek arc consistency can be readily parallelized; by invoking the arc consistency checks independently in parallel, one can achieve a linear parallel running time.

\[def:pacc\] An instance $({\mathbf{A}}, {\mathbf{B}})$ has the *peek arc consistency condition (PACC)* if for every element $a \in A$, there exists a homomorphism $h$ from ${\mathbf{A}}$ to ${\wp}({\mathbf{B}})$ such that $h(a)$ is a singleton.

\[prop:pacc\] The peek arc consistency algorithm does not reject an instance $({\mathbf{A}}, {\mathbf{B}})$ if and only if the instance has the PACC.

\[def:pac-solves\] Let ${\mathbf{B}}$ be a structure. We say that peek arc consistency *solves* ${{\mathsf{CSP}}}({\mathbf{B}})$ if for all structures ${\mathbf{A}}$, the following holds: $({\mathbf{A}}, {\mathbf{B}})$ has the PACC implies that there is a homomorphism ${\mathbf{A}}\rightarrow {\mathbf{B}}$.

The converse of the condition given in this definition always holds. Suppose that $h$ is a homomorphism from ${\mathbf{A}}$ to ${\mathbf{B}}$; then, the mapping taking each $a \in A$ to the singleton $\{ h(a) \}$ is a homomorphism from ${\mathbf{A}}$ to ${\wp}({\mathbf{B}})$ and hence $({\mathbf{A}}, {\mathbf{B}})$ has the PACC.

We use the notation ${\mathsf{Sing}}({\wp}({\mathbf{B}})^n)$ to denote the induced substructure of ${\wp}({\mathbf{B}})^n$ whose universe contains an $n$-tuple of ${\wp}({\mathbf{B}})^n$ if and only if at least one coordinate of the tuple is a singleton.

\[thm:pac-solves\] Let ${\mathbf{B}}$ be a structure. Peek arc consistency solves ${{\mathsf{CSP}}}({\mathbf{B}})$ if and only if for all $n \geq 1$ there is a homomorphism ${\mathsf{Sing}}({\wp}({\mathbf{B}})^n) \rightarrow {\mathbf{B}}$.

Singleton Arc Consistency {#ss:sac}
-------------------------

We now present the singleton arc consistency algorithm. As with arc consistency, this algorithm associates to each element $a \in A$ a set $S_a$ of feasible values. It then continually checks, for pairs $(a, b)$ with $a \in A$ and $b \in S_a$, whether or not arc consistency can be established with respect to the sets $S_a$ and when $a$ is assigned to $b$; if for some pair $(a, b)$ it cannot, then $b$ is removed from the set $S_a$. As with arc consistency, this algorithm’s outer loop runs until the sets $S_a$ stabilize, and the algorithm rejects if one of the sets $S_a$ is equal to the empty set.

[**Singleton Arc Consistency**]{}\

------------------------------------------------------------------------

denote $A=\{a_1,\ldots ,a_n\}$

Singleton arc consistency was introduced by Debruyne and Bessiere [@db-sac]. We now give a development of singleton arc consistency analogous to that of arc consistency and peek arc consistency.

\[def:sacc\] An instance $({\mathbf{A}}, {\mathbf{B}})$ has the *singleton arc consistency condition (SACC)* if there exists a mapping ${s: A \rightarrow {\wp}(B) \setminus \{ \emptyset \}}$ such that for all $a \in A$, $b \in s(a)$ there exists a homomorphism $h_{a,b}: {\mathbf{A}}\rightarrow {\wp}({\mathbf{B}})$ where:

-   $h_{a,b}(a)=\{b\}$, and

-   for all $a' \in A$, it holds that $h_{a,b}(a') \subseteq s(a')$.

\[prop:sacc\] The singleton arc consistency algorithm does not reject an instance $({\mathbf{A}}, {\mathbf{B}})$ if and only if the instance has the SACC.

Suppose that the singleton arc consistency algorithm does not reject an instance $({\mathbf{A}}, {\mathbf{B}})$. Let $\{ S_a \}_{a \in A}$ denote the sets computed by the algorithm at the point of termination, and define $s$ to be the mapping where $s(a) =S_a$ for all $a\in A$. Let $a \in A$ and $b \in s(a)$. By the definition of the algorithm, the pair $([{\mathbf{A}}, \{a_1\},\ldots,\{a_n\},\{a\}],\allowbreak[{\mathbf{B}}, S_{a_1},\ldots, S_{a_n},\{b\}])$ has the ACC, and thus the desired homomorphism $h_{a,b}$ exists.

Now, suppose that the instance $({\mathbf{A}}, {\mathbf{B}})$ has the SACC, and let $s$ be a mapping with the described properties. We show that throughout the execution of the algorithm, it holds that $s(a)\subseteq S_a$ for all $a\in A$. First, $S_a$ is initialized with $B$ for every $a\in A$. Next, we show that when $a \in A$ and $b \in s(a)$, then $b$ is never removed from $S_a$ by the algorithm. This is because by definition of SACC, there exists a homomorphism $h_{a,b}: {\mathbf{A}}\rightarrow {\wp}({\mathbf{B}})$ with $h_{a,b}(a)=\{b\}$ such that for all $a' \in A$, it holds that $h_{a,b}(a') \subseteq s(a')$. Since $s(a')\subseteq S_{a'}$ by the inductive assumption, $([{\mathbf{A}}, \{a_1\},\ldots,\{a_n\},\{a\}],[{\mathbf{B}}, S_{a_1},\ldots, S_{a_n},\{b\}])$ has the ACC and hence the algorithm does not remove $b$ from $S_a$.

\[def:sac-solves\] Let ${\mathbf{B}}$ be a structure. We say that singleton arc consistency *solves* ${{\mathsf{CSP}}}({\mathbf{B}})$ if for all structures ${\mathbf{A}}$, the following holds: $({\mathbf{A}}, {\mathbf{B}})$ has the SACC implies that there is a homomorphism ${\mathbf{A}}\rightarrow {\mathbf{B}}$.

The converse of the condition given in this definition always holds: suppose that $h$ is a homomorphism from ${\mathbf{A}}$ to ${\mathbf{B}}$. Then, the instance $({\mathbf{A}}, {\mathbf{B}})$ has the SACC via the mapping $s$ where $s(a) = \{ h(a) \}$ for all $a \in A$ and the mappings $h_{a, b}$ defined by $h_{a, b}(a') = \{ h(a') \}$ for all $a' \in A$.

We use the notation ${\mathsf{UnionSing}}({\wp}({\mathbf{B}})^n)$ to denote the induced substructure of ${\wp}({\mathbf{B}})^n$ whose universe contains an $n$-tuple $(S_1, \ldots, S_n)$ of ${\wp}({\mathbf{B}})^n$ if and only if it holds that $\bigcup_{i \in [n]} S_i = \bigcup_{i \in [n], |S_i| = 1} S_i$.

\[thm:sac-solves\] Let ${\mathbf{B}}$ be a structure. Singleton arc consistency solves ${{\mathsf{CSP}}}({\mathbf{B}})$ if and only if for all $n \geq 1$ there is a homomorphism ${\mathsf{UnionSing}}({\wp}({\mathbf{B}})^n) \rightarrow {\mathbf{B}}$.

First we show that if singleton arc consistency solves ${{\mathsf{CSP}}}({\mathbf{B}})$, then there is a homomorphism from ${\mathsf{UnionSing}}({\wp}({\mathbf{B}})^{n})$ to ${\mathbf{B}}$ for all $n\geq 1$. Let $n \geq 1$; we show that $({\mathsf{UnionSing}}({\wp}({\mathbf{B}})^{n}),{\mathbf{B}})$ has the SACC. Then, there is a homomorphism from ${\mathsf{UnionSing}}({\wp}({\mathbf{B}})^{n})$ to ${\mathbf{B}}$, since the singleton arc consistency algorithm solves [CSP(${\mathbf{B}}$)]{}.

Let $s$ be the mapping $s(a):=\bigcup_{i \in [n]} S_i$ for all tuples $a=(S_1,\dots,S_n)$ of ${\mathsf{UnionSing}}({\wp}({\mathbf{B}})^{n})$. Now let us consider an arbitrary tuple $a=(S_1,\dots,S_n)$ of ${\mathsf{UnionSing}}({\wp}({\mathbf{B}})^{n})$ and an arbitrary $b \in s(a)$. Since $\bigcup_{i \in [n]} S_i = \bigcup_{i \in [n], |S_i| = 1} S_i$, there is an $i\in[n]$ such that $\{b\}=S_i$. Thus, the homomorphism $\pi_i\colon {\mathsf{UnionSing}}({\wp}({\mathbf{B}})^{n}) \rightarrow {\wp}({\mathbf{B}})$ that projects onto the $i$th coordinate satisfies $\pi_i(a)=\{b\}$, and for all tuples $a'$ of ${\mathsf{UnionSing}}({\wp}({\mathbf{B}})^{n})$, it holds that $\pi_i(a')\subseteq s(a')$. Hence, $({\mathsf{UnionSing}}({\wp}({\mathbf{B}})^{n}),{\mathbf{B}})$ has the SACC.

For the other direction, we show that if there is a homomorphism from ${\mathsf{UnionSing}}({\wp}({\mathbf{B}})^{n})$ to ${\mathbf{B}}$ for all $n \geq 1$, then singleton arc consistency solves ${{\mathsf{CSP}}}({\mathbf{B}})$. Thus, we have to show that there exists a homomorphism from ${\mathbf{A}}$ to ${\mathbf{B}}$ if $({\mathbf{A}},{\mathbf{B}})$ has the SACC. Let $s$ be the homomorphism from the definition of SACC, and let us use $\{h_1,\ldots ,h_n\}$ to denote the set ${\{h_{a,b}\mid a\in A,b\in s(a)\}}$ of homomorphisms. Further, let $g$ be the homomorphism $(h_1,\ldots ,h_n) \colon {\mathbf{A}}\to {\wp}({\mathbf{B}})^{n}$. Now, for every element $a\in A$ the image $g(a)=(h_1(a),\ldots ,h_n(a))$ is a tuple of ${\mathsf{UnionSing}}({\wp}({\mathbf{B}})^{n})$: for every $b\in \bigcup_{j \in [n]} h_j(a)$, it holds that $b \in s(a)$ and thus there exists a homomorphism $h_{a,b}=h_i$ that maps $a$ to the singleton $\{b\}$; so, we have $\bigcup_{j \in [n]} h_j(a) = \bigcup_{i \in [n], |h_i(a)| = 1} h_i(a)$. Since $g$ is a homomorphism from ${\mathbf{A}}$ to ${\mathsf{UnionSing}}({\wp}({\mathbf{B}})^{n})$, we can compose $g$ and a homomorphism from ${\mathsf{UnionSing}}({\wp}({\mathbf{B}})^{n})$ to ${\mathbf{B}}$, which we know to exist by assumption, to get a homomorphism from ${\mathbf{A}}$ to ${\mathbf{B}}$. Consequently, singleton arc consistency solves ${{\mathsf{CSP}}}({\mathbf{B}})$.

Strength Comparison {#sect:comparison}
===================

In this section, we investigate relationships among the sets of structures solvable by the various algorithms presented. We show that for the structures having all constants, AC solves a strictly smaller set of structures than LAAC does; on the other hand, we show that there is a structure (not having all constants) solvable by AC but not LAAC. We then show that the structures solvable by AC or LAAC are strictly contained in those solvable by PAC; and, in turn, that the structures solvable by PAC are strictly contained in those solvable by SAC. We also show that the structures solvable by SAC (and hence, those solvable by any of the studied algorithms) all fall into the class of structures having *bounded width*; bounded width is a well-studied condition admitting multiple characterizations [@FederVardi; @LaroseZadori; @bkbw].

\[prop:all-constants-ac-implies-laac\] Suppose that ${\mathbf{B}}$ is a structure having all constants. If ${{\mathsf{CSP}}}({\mathbf{B}})$ is solvable by AC, then it is solvable by LAAC.

By Theorem \[thm:ac-solves\], there is a homomorphism $f: {\wp}({\mathbf{B}}) \rightarrow {\mathbf{B}}$. Since the structure ${\mathbf{B}}$ has all constants, for each $b \in B$ there is a relation symbol $R_b$ with $R_b^{{\mathbf{B}}} = \{ (b) \}$. Since $(\{ b \}) \in R_b^{{\wp}({\mathbf{B}})}$, it must hold that $f( \{ b \} ) \in R_b^{{\mathbf{B}}}$, from which it follows that $f( \{ b \} ) = b$. The mapping $l$ defined by $l(S, b) = f(S)$ is then a homomorphism of the type described in Theorem \[thm:laac-solves\].

There exists a structure ${\mathbf{B}}$ having all constants such that ${{\mathsf{CSP}}}({\mathbf{B}})$ is solvable by LAAC but not by AC.

Take ${\mathbf{B}}$ to be the relational structure with universe $\{ 0, 1 \}$ over signature $\{ U_0, U_1, R_{(0, 0)}, R_{(1, 1)} \}$ where $$U_0^{\mathbf{B}}= \{ 0 \}$$ $$U_1^{\mathbf{B}}= \{ 1 \}$$ $$R_{(0, 0)}^{\mathbf{B}}= \{ 0, 1 \}^2 \setminus \{ (0, 0) \}$$ $$R_{(1, 1)}^{\mathbf{B}}= \{ 0, 1 \}^2 \setminus \{ (1, 1) \}.$$ It is straightforward to verify that the mapping $l$ defined by $l(\{ 0, 1 \}, b') = b'$, $l(\{ 0 \}, b') = 0$, and $l(\{ 1 \}, b') = 1$ for all $b' \in \{ 0, 1 \}$ is a homomorphism from ${\wp}({\mathbf{B}}) \times {\mathbf{B}}$ to ${\mathbf{B}}$ satisfying the condition of Theorem \[thm:laac-solves\]. Hence, the problem ${{\mathsf{CSP}}}({\mathbf{B}})$ is solvable by LAAC.

To show that the problem ${{\mathsf{CSP}}}({\mathbf{B}})$ is not solvable by AC, let $f$ be an arbitrary mapping from ${\wp}(B) \setminus \{ \emptyset \}$ to $B$. We show that $f$ cannot be a homomorphism from ${\wp}({\mathbf{B}})$ to ${\mathbf{B}}$, which suffices by Theorem \[thm:ac-solves\]. Let $b = f(\{ 0, 1 \})$. It holds that $( \{ 0, 1 \}, \{ 0, 1 \} ) \in R_{(b, b)}^{{\wp}({\mathbf{B}})}$, but $(f(\{ 0, 1 \}), f(\{ 0, 1 \})) = (b, b) \notin R_{(b, b)}^{{\mathbf{B}}}$, and we are done.

There exists a structure ${\mathbf{B}}$ (not having all constants) such that ${{\mathsf{CSP}}}({\mathbf{B}})$ is solvable by AC but not by LAAC.

Take ${\mathbf{B}}$ to be the relational structure with universe $\{ 0, 1 \}$ over signature $\{ R, S \}$ where $R^{{\mathbf{B}}} = \{ 0, 1 \}^3 \setminus \{ (0, 1, 1) \}$ and $S^{{\mathbf{B}}} = \{ 0, 1 \}^3 \setminus \{ (1, 0, 0) \}$. The mapping $p$ that sends each element of ${\wp}(B) \setminus \{ \emptyset \}$ to $0$ is a homomorphism from ${\wp}({\mathbf{B}})$ to ${\mathbf{B}}$, and hence AC solves ${{\mathsf{CSP}}}({\mathbf{B}})$ by Theorem \[thm:ac-solves\].

To show that the problem ${{\mathsf{CSP}}}({\mathbf{B}})$ is not solvable by LAAC, let $f$ be an arbitrary mapping from $({\wp}(B) \setminus \{ \emptyset \}) \times B$ to $B$ that satisfies $f(\{ b \}, b') = b$ for all $b, b' \in B$. We show that $f$ cannot be a homomorphism from ${\wp}({\mathbf{B}}) \times {\mathbf{B}}$ to ${\mathbf{B}}$, which suffices by Theorem \[thm:laac-solves\]. We consider two cases depending on the value of $f( \{ 0, 1 \}, 0)$.

-   If $f( \{ 0, 1 \}, 0) = 1$, then we use the facts that $(\{ 0 \}, \{ 0, 1 \}, \{ 0, 1 \}) \in R^{{\wp}({\mathbf{B}})}$ and that $(0, 0, 0) \in R^{{\mathbf{B}}}$; we have that $(f( \{0 \}, 0), f( \{ 0, 1 \}, 0), f( \{ 0, 1 \}, 0)) = (0, 1, 1)$, which is not contained in $R^{{\mathbf{B}}}$, implying that $f$ is not a homomorphism of the desired type.

-   If $f( \{ 0, 1 \}, 0) = 0$, then we use the facts that $(\{ 1 \}, \{ 0, 1 \}, \{ 0, 1 \}) \in S^{{\wp}({\mathbf{B}})}$ and that $(0, 0, 0) \in S^{{\mathbf{B}}}$; we have that $(f( \{ 1 \}, 0), f( \{ 0, 1 \}, 0), f( \{ 0, 1 \}, 0)) = (1, 0, 0)$, which is not contained in $S^{{\mathbf{B}}}$, implying that $f$ is not a homomorphism of the desired type.

We now proceed to study PAC, and in particular, show that the structures solvable by AC or LAAC are solvable by PAC.

\[prop:ac-in-pac\] Let ${\mathbf{B}}$ be a structure. If ${{\mathsf{CSP}}}({\mathbf{B}})$ is solvable by AC, then it is also solvable by PAC.

Proposition \[prop:ac-in-pac\] follows directly from the algebraic characterizations given in Theorems \[thm:ac-solves\] and \[thm:pac-solves\]; it can also be seen to follow from the corresponding algorithm descriptions.

Let ${\mathbf{B}}$ be a structure. If ${{\mathsf{CSP}}}({\mathbf{B}})$ is solvable by LAAC, then it is also solvable by PAC.

Suppose that look-ahead arc consistency solves CSP(${\mathbf{B}}$). By Theorem \[thm:laac-solves\] there exists a homomorphism $l\colon {\wp}({\mathbf{B}}) \times {\mathbf{B}}\to {\mathbf{B}}$ such that $l( \{ b \}, b') = b$ for all $b, b' \in B$. We want to show that peek arc consistency solves CSP(${\mathbf{B}}$) by using Theorem \[thm:pac-solves\]. Thus, we have to show that for all $n \geq 1$ there is a homomorphism $g_n\colon {\mathsf{Sing}}({\wp}({\mathbf{B}})^n) \rightarrow {\mathbf{B}}$.

Let $n\geq 1$. Let us consider the mapping $g_n$ with $$g_n(S_1,\ldots ,S_n)=l(S_1,l(S_2,\ldots l(S_{n-1},l(S_n,b))\ldots ))$$ defined for all tuples $T=(S_1,\ldots ,S_n)\in {\mathsf{Sing}}({\wp}(B)^n)$ and all $b\in B$. First we want to show that $g_n$ is well defined. Let $b_1,b_2\in B$ with $b_1\not = b_2$, let $(S_1,\ldots ,S_n)\in {\mathsf{Sing}}({\wp}(B)^n)$ and let $i\in[n]$ be an index such that $S_i$ is a singleton. Let $S_i=\{b_*\}$ for a $b_*\in B$. We obtain that $$\begin{aligned}
&    l(S_1,\ldots l(S_{i-1},l(S_{i},\ldots l(S_{n-1},l(S_n,b_1))\ldots ))\ldots )\\
=\;&   l(S_1,\ldots l(S_{i-1},l(S_{i},b'))\ldots )\\
=\;&   l(S_1,\ldots l(S_{i-1},b_*)\ldots )
\intertext{with $b'=l(S_{i+1},\ldots l(S_{n-1},l(S_n,b_1))\ldots )\in B$, because $l$ is applied to
the singleton $S_i=\{b_*\}$ and $b'$. 
Similarly, we obtain that}
&    l(S_1,\ldots l(S_{i-1},l(S_{i},\ldots l(S_{n-1},l(S_n,b_2))\ldots ))\ldots )\\
=\;&   l(S_1,\ldots l(S_{i-1},b_*)\ldots )\end{aligned}$$ Consequently, $g_n$ is well defined. Next, we prove that $g_n$ is a homomorphism. Let $R^{{\mathsf{Sing}}({\wp}({\mathbf{B}})^n)}$ be a $k$-ary relation and let $(T^1,\ldots ,T^k)$ be a tuple in this relation. Denote $T^i=(S^i_1,S^i_2,\ldots ,S^i_n)$ for all $i\in[k]$; then, $S'_j=(S^1_j,\ldots ,S^k_j)$ has to be in $R^{{\wp}({\mathbf{B}})}$ for all $j\in[n]$. Further, we know that there exists a tuple $\bar{b}=(b_1,\ldots ,b_k)\in R^{\mathbf{B}}$, because $R^{{\wp}({\mathbf{B}})}$ is not empty. Since $l$ is a homomorphism, the tuple $$g_n(S'_1, S'_2, \ldots, S'_n)=l(S'_1, l(S'_2, \ldots
l(S'_{n-1},l(S'_n,\bar{b}))\ldots ))$$ is in $R^{{\mathbf{B}}}$. Thus, $g_n$ is a homomorphism from ${\mathsf{Sing}}({\wp}({\mathbf{B}})^{n})$ to ${\mathbf{B}}$.

There exists a structure ${\mathbf{B}}$ having all constants such that ${{\mathsf{CSP}}}({\mathbf{B}})$ is solvable by PAC but not by LAAC nor AC.

Let us consider the structure with universe $\{0,1,2\}$ over the signature $\{U_0,U_1,U_2,R_1,R_2\}$ where $$U_0^{\mathbf{B}}=\{(0)\}$$ $$U_1^{\mathbf{B}}=\{(1)\}$$ $$U_2^{\mathbf{B}}=\{(2)\}$$ $$R_1^{\mathbf{B}}= \big(\{0,1\}\times\{0,1,2\}\big)  \setminus  \{(0,0)\}$$ $$R_2^{\mathbf{B}}=\{(0,0),(1,2),(2,1)\}.$$ First we show that there is no homomorphism $l: {\wp}({\mathbf{B}})\times{\mathbf{B}}\to{\mathbf{B}}$ such that $l(\{b\},b')=b$ for all $ b,b'$. Let us assume there is one. Since $(\{0\},\{1,2\})\in R_1^{{\wp}({\mathbf{B}})}$ and $(1,0)\in R_1^{\mathbf{B}}$ the tuple $( l(\{0\},1),l(\{1,2\},0))$, which is equal to $(0,l(\{1,2\},0))$, has to be contained in $R_1^{\mathbf{B}}$. Thus, $l(\{1,2\},0)$ cannot be equal to $0$. On the other hand, $(\{1,2\},\{1,2\})\in R_2^{{\wp}({\mathbf{B}})}$ and $(0,0)\in R_2^{\mathbf{B}}$ implies that $(l(\{1,2\},0),l(\{1,2\},0))$ is in $R_2^{\mathbf{B}}$. Therefore, $l(\{1,2\},0)$ has to be $0$, which is a contradiction. This establishes that the structure is not solvable by LAAC; by Proposition \[prop:all-constants-ac-implies-laac\], it follows that the structure is not solvable by AC.

Next we show that for all $n$, there exists a homomorphism $f$ from ${\mathsf{Sing}}({\wp}({\mathbf{B}})^n)$ to ${\mathbf{B}}$. Let $n$ be arbitrary and let $(S_1,\dots,S_n)$ be an arbitrary $n$-tuple of ${\mathsf{Sing}}({\wp}({\mathbf{B}})^n)$. Further, let $i$ be the minimal number such that $S_i$ is $\{1\}$, $ \{2\}$, $ \{0,1\}$ or $\{0,2\}$; if such an $S_i$ does not exists, then $i=0$. The homomorphism $f$ can be defined as follows: $$f(S_1,\dots,S_n)=
\begin{cases}
1 & \text{if  $i>0$ and $S_i$ is $\{1\}$ or $\{0,1\}$}\\
2 & \text{if  $i>0$ and $S_i$ is $\{2\}$ or $\{0,2\}$}\\
0 & \text{otherwise.}\\
\end{cases}$$ Let us verify that $f$ is indeed a homomorphism: First of all, it is easy to see that $f(S_1,\dots,S_n)$ is in $U_i^{{\mathbf{B}}}$ whenever $(S_1,\dots,S_n)$ is in $U_i^{{\mathsf{Sing}}({\wp}({\mathbf{B}})^n)}$. Next, let us consider $R_2$. Let $(S_1,\dots,S_n)$ and $(T_1,\dots,T_n)$ be arbitrary $n$-tuples of ${\mathsf{Sing}}({\wp}({\mathbf{B}})^n)$ such that $(S_l,T_l)$ is in $R_2^{{\wp}({\mathbf{B}})}$ for all $l$. Let $i$ be the minimal number such that $S_i$ is $\{1\}$, $\{2\}$, $\{0,1\}$ or $\{0,2\}$, and let $j $ be the minimal number such that $T_j$ is $\{1\}$, $\{2\}$, $\{0,1\}$ or $\{0,2\}$, and if such an $S_i $ or $T_j$ does not exists, then $i=0$ or $j=0$ respectively. If $i > 0$, then $T_i$ has to be $\{1\}$, $\{2\}$, $\{0,1\}$ or $\{0,2\}$ and hence $0<j \leq i$. Symmetrically, if $j > 0$, then $0<i \leq j$. Therefore, $i = j$. Now, if $i = j = 0$, then $(f(S_1,\dots,S_n), f(T_1,\dots,T_n)) = (0,0)$, which is in $R_2^{{\mathbf{B}}}$; if $i = j > 0$, then $(f(S_1,\dots,S_n), f(T_1,\dots,T_n)) \in R_2^{{\mathbf{B}}}$ follows directly from $(S_i,T_i)$ being in $R_2^{{\wp}({\mathbf{B}})}$. Finally, let us consider two arbitrary $n$-tuples $(S_1,\dots,S_n)$ and $(T_1,\dots,T_n)$ of ${\mathsf{Sing}}({\wp}({\mathbf{B}})^n)$ such that $(S_l,T_l)$ is in $R_1^{{\wp}({\mathbf{B}})}$ for all $l$. If $f(S_1,\dots,S_n)=2$, then $S_i=\{2\}$ or $\{0,2\}$ and $(S_i,T_i)$ cannot be in $R_1^{{\wp}({\mathbf{B}})}$. If $f(S_1,\dots,S_n)=1$, then $(f(S_1,\dots,S_n), f(T_1,\dots,T_n) )$ is in $\{1\}\times\{0,1,2 \}$ and, thus, in $R_1^{{\mathbf{B}}}$. If $j=0$, then let $k$ be an index such that $T_k=\{0\}$. Such an index has to exist, because $(T_1,\dots,T_n)$ is a tuple of ${\mathsf{Sing}}({\wp}({\mathbf{B}})^n)$. Since $(S_k,T_k)$ is in $R_1^{{\wp}({\mathbf{B}})}$, $S_k$ has to be $\{1\}$, and hence $f(S_1,\dots.,S_n) \in\{1,2\}$, and we appeal to one of the first two cases. The remaining case is $i = 0$ and $j>0$. In this case, $(f(S_1,\dots,S_n), f(T_1,\dots,T_n) )$ is in $\{0\}\times\{1,2 \}$ and therefore in $R_1^{{\mathbf{B}}}$.

We now move on to study SAC; we show that SAC is strictly more powerful than PAC.

\[prop:pac-in-sac\] Let ${\mathbf{B}}$ be a structure. If ${{\mathsf{CSP}}}({\mathbf{B}})$ is solvable by PAC, then it is also solvable by SAC.

Proposition \[prop:pac-in-sac\] follows directly from the algebraic characterizations given in Theorems \[thm:pac-solves\] and \[thm:sac-solves\]; it can also be seen to follow from the corresponding algorithm descriptions.

There exists a structure ${\mathbf{B}}$ having all constants such that ${{\mathsf{CSP}}}({\mathbf{B}})$ is solvable by SAC but not by PAC.

We will consider a structure that has as a polymorphism the idempotent binary commutative operation ${*}$ defined on the set $\{ 0, 1, 2, 3 \}$ by $1 {*}2 = 2$, $2 {*}3 = 3$, $3 {*}1 = 1$, and $0 {*}a = a$ for all $a \in \{ 1, 2, 3 \}$. We consider the structure ${\mathbf{B}}$ with universe $\{ 0, 1, 2, 3 \}$ over the signature $\{U_0, U_1, U_2, U_3, R_1, R_2 \}$ where we have $$U_0^{{\mathbf{B}}} = \{ (0) \}$$ $$U_1^{{\mathbf{B}}} = \{ (1) \}$$ $$U_2^{{\mathbf{B}}} = \{ (2) \}$$ $$U_3^{{\mathbf{B}}} = \{ (3) \}.$$ $$R_1^{{\mathbf{B}}} = \{ 0, 1, 2, 3 \}^2 \setminus \{ (0, 0) \},$$ $$R_2^{{\mathbf{B}}} = \{ (1, 2), (2, 3), (3, 1), (0, 0) \}$$ It is straightforward to verify that this structure ${\mathbf{B}}$ has the operation ${*}$ as a polymorphism. The solvability of ${\mathbf{B}}$ follows from Theorem \[thm:twosem-sac\], which is proved in the next section; see also the discussion in Example \[ex:twosem\].

To show that peek arc consistency does not solve ${{\mathsf{CSP}}}({\mathbf{B}})$, we prove that there is no homomorphism from ${\mathsf{Sing}}({\wp}({\mathbf{B}})^2)$ to ${\mathbf{B}}$, which is sufficient by Theorem \[thm:pac-solves\]. Define ${\overline{t_1}} = ( \{ 0 \}, \{ 1, 2, 3 \} )$ and ${\overline{t_2}} = (\{ 1, 2, 3 \}, \{ 0 \} )$. It is straightforward to verify that $({\overline{t_1}}, {\overline{t_2}}) \in R_1^{{\wp}({\mathbf{B}})^2}$; since each of the tuples ${\overline{t_1}}, {\overline{t_2}}$ contains a singleton, it holds that $({\overline{t_1}}, {\overline{t_2}}) \in R_1^{{\mathsf{Sing}}({\wp}({\mathbf{B}})^2)}$. Assume, for a contradiction, that $h$ is a homomorphism from ${\mathsf{Sing}}({\wp}({\mathbf{B}})^2)$ to ${\mathbf{B}}$. It then holds that $(h({\overline{t_1}}), h({\overline{t_2}})) \in R_1^{{\mathbf{B}}}$. Since $(0, 0) \notin R_1^{{\mathbf{B}}}$, we have that one of the values $h({\overline{t_1}}), h({\overline{t_2}})$ is not equal to $0$. Let us assume that $h({\overline{t_1}})$ is not equal to $0$; the other case is symmetric. Denote $h({\overline{t_1}})$ by $b$; we have $b \in \{ 1, 2, 3 \}$. Since each of the two tuples $( \{ 0 \}, \{ 0 \} )$, $( \{ 1, 2, 3 \}, \{ 1, 2, 3 \} )$ is contained in $R_2^{{\wp}({\mathbf{B}})}$, we have that $(( \{ 0 \}, \{ 1, 2, 3 \} ), ( \{ 0 \}, \{ 1, 2, 3 \} ))
\in R_2^{{\mathsf{Sing}}({\wp}({\mathbf{B}})^2)}$. It follows that $( b, b ) \in R_2^{{\mathbf{B}}}$, but since no tuple of the form $(c, c)$ with $c \in \{ 1, 2, 3 \}$ is contained in $R_2^{{\mathbf{B}}}$, we have reached our contradiction.

We close this section by showing that the structures solvable by SAC, and hence those solvable by any of the algorithms studied here, fall into the class of structures having *bounded width*. We begin by defining bounded width. A [*partial homomorphism*]{} from ${\mathbf{A}}$ to ${\mathbf{B}}$ is a mapping $f:A'\rightarrow B$, where $A'\subseteq A$, that defines a homomorphism to ${\mathbf{B}}$ from the substructure of ${\mathbf{A}}$ induced by $A'$. When $f$ and $g$ are partial homomorphisms we say that $g$ [*extends*]{} $f$, denoted by $f\subseteq g$, if ${\mathrm{Dom}}(f)\subseteq{\mathrm{Dom}}(g)$ and $f(a)=g(a)$ for every $a\in{\mathrm{Dom}}(f)$.

Let $k>1$. A [*$k$-strategy*]{} for an instance $({\mathbf{A}},{\mathbf{B}})$ is a nonempty collection $H$ of partial homomorphisms from ${\mathbf{A}}$ to ${\mathbf{B}}$ satisfying the following conditions:

1.  (restriction condition) if $f\in H$ and $g\subseteq f$, then $g\in H$;

2.  (extension condition) if $f\in H$, $|{\mathrm{Dom}}(f)|<k$, and $a\in A$, there is $g\in H$ such that $f\subseteq g$ and $a\in{\mathrm{Dom}}(g)$.

When $H$ is a $k$-strategy for $({\mathbf{A}},{\mathbf{B}})$ and $a_1,\dots,a_j\in A$ is a sequence, we define $H_{a_1,\dots,a_j}\subseteq B^j$ to be the relation $$\{(f(a_1),\dots,f(a_j)) ~|~ f\in H, {\mathrm{Dom}}(f)=\{a_1,\dots,a_j\}\}.$$

Let ${\mathbf{B}}$ be a structure and $k \geq 1$. We say that ${{\mathsf{CSP}}}({\mathbf{B}})$ has [*width*]{} $k$ if for all structures ${\mathbf{A}}$ the following holds: if there is a $(k+1)$-strategy for $({\mathbf{A}},{\mathbf{B}})$ then there is a homomorphism ${\mathbf{A}}\rightarrow{\mathbf{B}}$. We say that ${{\mathsf{CSP}}}({\mathbf{B}})$ has [*bounded width*]{} if it has width $k$ for some $k \geq 1$.

Let ${\mathbf{B}}$ be a structure. If ${{\mathsf{CSP}}}({\mathbf{B}})$ is solvable by SAC, then ${{\mathsf{CSP}}}({\mathbf{B}})$ has bounded width.

Let $r$ be the maximum of all the arities of the signature of ${\mathbf{B}}$, and set $k = \max(2, r+1)$. We shall show that for any instance ${\mathbf{A}}$ of ${{\mathsf{CSP}}}({\mathbf{B}})$, if $H$ is a $k$-strategy for $({\mathbf{A}},{\mathbf{B}})$, then the instance $({\mathbf{A}},{\mathbf{B}})$ has the SACC, which suffices.

Let us define the mapping $s:A\rightarrow {\wp}(B)\setminus\{ \emptyset \}$ as $s(a)=H_a$. Furthermore, for every $a\in A$, $b\in s(a)$, define $h_{a,b}: A \rightarrow {\wp}(B)\setminus\{\emptyset\}$ as the mapping $h_{a,b}(a')=\{b' ~|~ (b,b')\in H_{a,a'} \}$. Note that the extension property of $H$ guarantees that, for every $a'\in A$, $h_{a,b}(a')$ is, indeed, nonempty. It follows from the definition of $h_{a,b}$ that $h_{a,b}(a)=\{b\}$, and that for all $a' \in A$, $h_{a,b}(a') \subseteq s(a')$.

It is only necessary to show that $h_{a,b}$ defines a homomorphism from ${\mathbf{A}}$ to ${\wp}({\mathbf{B}})$. Let $R^{{\mathbf{A}}}$ be any relation in ${\mathbf{A}}$, let $(a_1,\dots,a_i)\in R^{{\mathbf{A}}}$, and let $S_j=h_{a,b}(a_j)$ for each $j \in [i]$. In order to prove that $(S_1,\dots,S_i)\in R^{{\wp}({\mathbf{B}})}$ it suffices to show that for every $j\in [i]$ and every $b_j\in S_j$, there exists some $(c_1,\dots,c_i)\in R^{{\mathbf{B}}} \cap (S_1\times\cdots\times S_i)$ with $c_j=b_j$. This is a direct consequence of the properties of the strategy. Indeed, by the definition of $h_{a,b}$ we know that $(b,b_j)\in H_{a,a_j}$ and then, by an iterative application of the extension property, we can show that there exists an extension $(b,c_1,\dots,c_i)\in H_{a,a_1,\dots,a_i}$ with $c_j=b_j$. The fact that $H$ contains only partial homomomorphisms guarantees that $(c_1,\dots,c_i)\in R^{\mathbf{B}}$. Finally, it follows from the restriction condition that for every $l \in [i]$, we have $c_l\in S_{l}$.

Tractability via singleton arc consistency {#sect:tractability}
==========================================

Majority operations
-------------------

An operation $m\colon B^3\to B$ is a *majority* operation if it satisfies the identity $m(x,y,y)=m(y,x,y)=m(y,y,x)=y$ for all $x,y\in B$. Relative to a majority operation $m \colon B^3 \to B$, when $I \subseteq J \subseteq B$, we say that $I$ is an *ideal* of $J$ if for every $x,y,z\in J$ such that $x,z\in I$ we have $m(x,y,z)\in I$. We will establish the following result.

\[the:SACCmajority\] If ${\mathbf{B}}$ is a structure that has a majority polymorphism, then singleton arc consistency solves ${{\mathsf{CSP}}}({\mathbf{B}})$.

The proof is obtained by using a strengthened version of the Prague strategy defined by Barto and Kozik [@bkbw].

In this section, for the sake of readability, we will typically use the notation $t[i]$ to denote the $i$th entry of a tuple $t$.

We introduce the following definitions relative to an instance $({\mathbf{A}}, {\mathbf{B}})$ with signature $\sigma$. A *pattern* $p$ of ${\mathbf{A}}$ is a sequence $a_1,e_1,a_2,\dots,e_{m-1},a_m$ such that $a_1,\dots,a_m$ are elements of $A$ and for every $n \in [m-1]$, we have that $e_n$ is a triple $(R,i,j)$ where $R$ is a symbol in $\sigma$ and $i,j$ are indices such that there is a tuple $t\in R^{{\mathbf{A}}}$ with $t[i]=a_n$ and $t[j]=a_{n+1}$. The [*length*]{} of pattern $p$ is defined to be $m$. A pattern is a *cycle* if $a_1=a_m$. By a *set system*, we mean any mapping $H: A \rightarrow {\wp}(B) \setminus \{ \emptyset \}$.

A pattern $q = b_1,e'_1,\dots,e'_{m-1},b_m$ of ${\mathbf{B}}$ having the same length as a pattern $p$ of ${\mathbf{A}}$ is a [*realization*]{} of $p$ if $e_n=e'_n$ for all $n \in [m-1]$. The pair $(b_1,b_m)$ is said to be a [*support*]{} of $p$. For a set system $H$, if it holds that $b_n\in H(a_n)$ for all $n\in [m]$ then $(b_1,b_m)$ is said to be a support of $p$ [*inside*]{} $H$.

A set system $H$ is a *weak strategy* if for every pattern $p=a_1,e_1,\dots,e_{m-1},a_m$ of ${\mathbf{A}}$, and every $b_1\in H(a_1)$ there exists some $b_m\in H(a_m)$ such that $(b_1,b_m)$ supports $p$ inside $H$. A set system $H$ is a *strong strategy* if for every cycle $p=(a=a_1,\dots,a_m=a)$ in ${\mathbf{A}}$ and every $b\in H(a)$, the pair $(b,b)$ supports $p$ inside $H$. Note that every strong strategy is a weak strategy and that the class of weak strategies remains the same if, in the definition of weak strategy, one replaces “every pattern $p=a_1,e_1,\dots,e_{m-1},a_m$” by “every pattern $p=a_1,e_1,\dots,e_{m-1},a_m$ of length $m=2$”.

\[obs:arcconsistency\] Every strong strategy is a weak strategy, relative to an instance $({\mathbf{A}}, {\mathbf{B}})$.

For a pattern $p=a_1,e_1,\dots,e_{m-1},a_m$ of ${\mathbf A}$, one needs only to apply the definition of strong strategy to the the pattern $a_1,e_1,\dots,e_{m-1},a_m,e_{m-1}^{-1},a_{m-1},\dots,e_1^{-1},a_1$, where $(R,i,j)^{-1}$ is defined to be $(R,j,i)$.

\[le:SACCtostrong\] There exists a strong strategy for an instance $({\mathbf{A}}, {\mathbf{B}})$ having the SACC.

Let $s: A \rightarrow {\wp}(B) \setminus \{ \emptyset \}$, $\{ h_{a, b} \}$ be the mappings witnessing that $({\mathbf{A}},{\mathbf{B}})$ has the SACC. We claim that the set system $H$ defined by $H(a)=s(a)$ for all $a\in A$ is a strong strategy. Indeed, let $p=a_1,e_1,\dots,a_m$ be a pattern of $A$ with $a_1=a_m=a$ and let $b\in H(a_1)$. We claim that there exists a realization $b_1,e_1,\dots,b_m$ of $p$ with $b_1=b_m=b$ such that for every $1\leq n\leq m$, $b_n\in h_{a,b}(a_n)$. The realization is constructed in an inductive manner. First, set $b_1$ to $b$. Assume now that $b_{n-1}$ is already set and let $e_{n-1}$ be $(R,i,j)$. There exists a tuple $(x_1,\dots,x_r)\in R^{{\mathbf{A}}}$ such that $x_i=a_{n-1}$ and $x_j=a_n$. Since $h_{a,b}$ is a homomorphism, the subset $S\subseteq B^r$ defined by $\pi_l S=h_{a,b}(x_l)$ for every $1\leq l\leq r$ is a subset of $R^{{\mathbf{B}}}$. From $b_{n-1}\in h_{a,b}(x_i)$ it follows that there exists a tuple $(y_1,\dots,y_r)\in S$ with $y_i=b_{n-1}$. Define $b_n$ to be $y_j$. Since, by definition of SACC strategy $h_{a,b}(a)=\{b\}$, it follows that $b_m=b$.

We now prove the following lemma, which, as we explain after the proof, essentially establishes the desired theorem. In the course of proving this lemma, we establish a number of observations.

By a minimal strong strategy, we mean minimal with respect to the ordering where for two strategies $H, H'$, we consider $H \subseteq H'$ if $H(a) \subseteq H'(a)$ for all $a \in A$.

\[le:singletonstrong\] If the relations of ${\mathbf{B}}$ are invariant under a majority operation $\phi$ and $H$ is a minimal strong strategy then for every $a \in A$, the set $H(a)$ is a singleton.

Towards a contradiction assume that $H$ is a minimal strong strategy and $a^* \in A$ is such that $H(a^*)$, is not a singleton. Consider the digraph $G$ whose nodes are of the form $(a,C)$ with $a\in A$ and $C\subseteq H(a)$, and there is an edge from $(a,C)$ to $(a',C')$ if there is a pattern $p=a_1,\dots,a_m$ with $a=a_1$ and $a'=a_m $ in ${\mathbf A}$ such that the following holds: $C'$ is the set containing all $b'\in H(a')$ such that $(b,b')$ is supported by $p$ inside $H$ for some $b\in C$.

\[observation3\] Let $p=a_1,e_1,\dots,a_m$ be a pattern, let $1<i<m$, let $q$ be the pattern $a_1,e_1,\dots,a_i$ and $r$ be the pattern $a_i,e_i\dots,e_m$. If $q$ defines an edge from $(a_1,C_1)$ to $(a_i,C_i)$ and $r$ defines an edge from $(a_i,C_i)$ to $(a_m,C_m)$ then $p$ defines an edge from $(a_1,C_1)$ to $(a_m,C_m)$. Hence, the graph $G$ is transitive.

The following observation follows from the definition of strong strategy.

\[observation1\] If there is an edge from $(a,C)$ to $(a,C')$ in $G$, then necessarily $C\subseteq C'$.

\[observation2\] If there is an edge from $(a,C)$ to $(a',C')$ in $G$, and $C$ is an ideal of $H(a)$, then $C'$ is an ideal of $H(a')$.

\[ (Observation \[observation2\])\] Let us prove the claim by induction on the length $m$ of the pattern that defines the edge.

Assume first that $m=2$. Let $a,(R,i,j),a'$ be any such pattern. Let $x_1,x_2,x_3\in H(a')$ and assume that two of them, say $x_1,x_3$, belong to $C'$. It follows, by the definition of edge, that for every $n\in\{1,3\}$ there exists tuple $t_n\in R^{{\mathbf{B}}}$ with $t_n[j]=x_n$ and $t_n[i]\in C$. Also, it follows by considering pattern $a',(R,j,i),a$ and from the fact that $H$ is a weak strategy that there exists a tuple $t_2\in R^{{\mathbf{B}}}$ with $t_2[i]\in H(a)$ and $t_2[j]=x_2$. Consider now tuple $t=\phi(t_1,t_2,t_3)$. Since $C$ is an ideal of $H(a)$ we have that $t[i]\in C$. Hence, we conclude that $\phi(x_1,x_2,x_3)=t[j]\in C'$.

The case $m>2$ follows from the inductive hypothesis and Observation \[observation3\].

Now, let $G'$ be the subgraph of $G$ induced by all nodes $(a,C)$ such that $C$ is an ideal of $H(a)$ and $C\neq H(a)$. Observe that as $H(a^*)$ is not a singleton, the graph $G'$ is nonempty, because every singleton is an ideal.

A subset $M$ of vertices of a directed graph is a *strongly connected component* if for every pair $(v,w)\in M^2$ there exists a path from $v$ to $w$ consisting only of vertices in $M$. It is a *maximal strongly connected component* if additionally, there is no edge $(v,w)$ with $v\in M$ and $w\not\in M$.

Let $M$ be a maximal strongly connected component of $G'$. The following observation is a direct consequence of Observations \[observation3\] and \[observation1\].

\[observation4\] The maximal strongly connected component $M$ cannot have two vertices $(a,C)$, $(a,C')$ with $C\neq C'$.

We shall construct a new strong strategy $H'$ as follows. If $(a,C)$ belongs to $M$, then set $H'(a)=C$ otherwise set $H'(a)=H(a)$. Clearly $H'$ is strictly smaller than $H$.

We shall start by showing that $H'$ is a weak strategy. By the note following the definition of weak strategy it is only necessary to show that for every pattern $p=a_1,e_1,a_2$ of length $2$ of ${\mathbf{A}}$ and every $b_1\in H'(a_1)$, there exists a support $(b_1,b_2)$ of $p$ inside $H'$.

We do a case analysis. If $(a_2,H'(a_2))$ does not belong to $M$ the claim follows from the fact that $H$ is a weak strategy. Assume now that $(a_2,H'(a_2))$ belongs to $M$. Consider the pattern $p=a_2,e_1^{-1},a_1$ where $(R,i,j)^{-1}=(R,j,i)$. This pattern defines an edge (in $G$) from $(a_2,H'(a_2))$ to a node $(a_1,C)$. Observe, that by the definition of the edges of $G$, we know that for every element $b\in C$ there is some $b'\in H'(a_2)$ such that $(b,b')$ is supported by $p$ inside $H$. Hence we only need to show that $H'(a_1)\subseteq C$.

If $(a_1,C)$ is in $G'$ then, since $M$ is a maximal strongly connected component of $G'$, we have that $(a_1,C)$ belongs to $M$ as well and hence $C=H'(a_1)$. If $(a_1,C)$ is not in $G'$ this must be because $C$ is not an ideal of $H(a_1)$ or because $C=H(a_1)$. We can rule out the first possibility in the following way: by the definitions of $G'$ and $H'$, $H'(a_2)$ is an ideal of $H(a_2)$. It follows by observation \[observation2\] that $C$ is an ideal of $H(a_1)$. In consequence $C=H(a_1)$ and the proof that $H'$ is a weak strategy is concluded.

It remains to show that $H'$ is a strong strategy. Let $p=a_1,e_1,\dots,e_{m-1},a_m$ be any cycle in $\mathbf A$ with $a_1=a_m=a$ and let $b$ be any element in $H'(a)$. Since $H'$ is a weak strategy we know that there is a realization $b_1,\dots,b_m$ of $p$ with $b_1=b$ inside $H'$. Notice that we do not necessarily have $b_m = b$. Symmetrically, by considering pattern $a_m,e^{-1}_{m-1}, \ldots, e^{-1}_1,a_1$ we know that there is a realization $d_m,e^{-1}_{m-1}, \ldots, e^{-1}_1,d_1$ of $p$ with $d_m=b$ inside $H'$. Also, since $H$ is a strong strategy we know that there exists a realization $c_1,e_1,\dots,c_m$ of $p$ such that $c_1=c_m=b$ inside $H$ (but not necessarily inside $H'$). Finally consider the sequence $x_1,\dots,x_m$ defined by $x_j=\phi(b_j,c_j,d_j), 1\leq j\leq m$. This sequence is a realization of $p$. Furthermore, we have that $x_1=x_m=b$. It remains to show that it is inside $H'$. Indeed, for every $1\leq j\leq m$, $\{b_j,d_j\}\subseteq H'(a_j)$ and $c_j\in H(a_j)$. Since $H'(a_j)$ is an ideal of $H(a_j)$ the claim follows.

(Theorem \[the:SACCmajority\]) Suppose that the instance $({\mathbf{A}}, {\mathbf{B}})$ has the SACC and that ${\mathbf{B}}$ has the majority polymorphism $\phi$. By Lemmas \[le:SACCtostrong\] and \[le:singletonstrong\] there exists a strong strategy $H$ for $({\mathbf{A}}, {\mathbf{B}})$ such that $H(a)$ is a singleton for every $a\in A$. Consider now the mapping $h: A\rightarrow B$ that maps every $a\in A$ to the only element in $H(a)$. We claim that $h$ is a homomorphism from ${\mathbf{A}}$ to ${\mathbf{B}}$. Indeed, let $R$ be any relation symbol, and $(a_1,\dots,a_r)$ be any tuple in $R^{{\mathbf{A}}}$. Fix any $1\leq i,j\leq r$ and consider pattern $a_i,(R,i,j),a_j$. It follows by the definition of strong strategy that there is a $t\in R^{{\mathbf{B}}}$ such that $t[i]=h(i)$ and $t[j]=h(j)$. Since $R^{{\mathbf{B}}}$ is necessarily $2$-decomposable [@CCC], $h$ is a homomorphism.

2-semilattice operations
------------------------

A 2-semilattice ${\mathbb{G}}= (G, {\star})$ consists of a set $G$, which in this paper we assume to be finite, and a binary operation ${\star}$ satisfying $x {\star}x = x$ (idempotency), $x {\star}y = y {\star}x$ (commutativity), and $x {\star}(x {\star}y) = (x {\star}x) {\star}y$ (restricted associativity).

Each 2-semilattice naturally induces a directed graph $(G, E)$ where $(a, b) \in E$ if and only if $a {\star}b = b$. When $(a,b)\in E$, we also write $a \leq b$. The graph $(G,E)$ is connected, since $a {\star}(a {\star}b) = b {\star}(a {\star}b) = a {\star}b$ for any $a,b\in G$, and therefore, $a,b \leq a {\star}b$. Each 2-semilattice has a unique maximal strongly connected component, that is a strongly connected component with no outgoing edges, denoted by ${\overline{G}}$. The component ${\overline{G}}$ is also the unique strongly connected component of $(G, E)$ such that for any $a \in G$, there exists $b \in {\overline{G}}$ such that $a \leq b$. In this section, we will prove that a certain class of 2-semilattices is tractable via singleton arc consistency. Our treatment of 2-semilattices is inspired and influenced by the study conducted by Bulatov [@twosemilattices], who proved that they are polynomial-time tractable.

A 2-semilattice ${\mathbb{G}}= (G, {\star})$ is an algebra. By an *algebra*, we mean a pair $(A, O)$ consisting of a set $A$, the *universe* of the algebra, and a set $O$ of operations on $A$. A *congruence* of an algebra is an equivalence relation preserved by the operation(s) of the algebra, and an algebra is *simple* if its only congruences are trivial (that is, if its only congruences are the equality relation on $A$ and $A \times A$, where $A$ is the universe of the algebra).

We will begin by proving some general results on singleton arc consistency. In the following discussion, a *subalgebra* is defined, with respect to a relational structure ${\mathbf{B}}$, as a subset $S \subseteq B$ that is preserved by all polymorphisms of ${\mathbf{B}}$. For an arbitrary subset $T \subseteq B$, we use ${\langle}T {\rangle}$ to denote the smallest subalgebra containing $T$.

\[prop:poly-ac\] Suppose that $g_1, \ldots, g_k: {\mathbf{A}}\rightarrow {\wp}({\mathbf{B}})$ are homomorphisms, and suppose that $f: B^k \rightarrow B$ is a polymorphism of ${\mathbf{B}}$. Then the map $g: A \rightarrow {\wp}(B) \setminus \{ \emptyset \}$ defined by $g(a) = f(g_1(a), \ldots, g_k(a))$ for all $a \in A$ is a homomorphism ${\mathbf{A}}\rightarrow {\wp}({\mathbf{B}})$.

For an operation $f: B^k \rightarrow B$ and a sequence of subsets $B_1, \ldots, B_k \subseteq B$, by the notation $f(B_1, \ldots, B_k)$, we denote the set $\{ f(b_1, \ldots, b_k) ~|~ b_1 \in B_1, \ldots, b_k \in B_k \}$. Regarding this notation, it is easy to verify that $f$ can be understood as a polymorphism of ${\wp}({\mathbf{B}})$ if $f$ is a polymorphism of ${\mathbf{B}}$. Proposition \[prop:poly-ac\] follows straightforwardly from the definitions.

\[prop:subalgebra-ac\] Suppose that $h: {\mathbf{A}}\rightarrow {\wp}({\mathbf{B}})$ is a homomorphism. Then the map $h'$ defined by $h'(a) = {\langle}h(a) {\rangle}$ for all $a \in A$ is also a homomorphism ${\mathbf{A}}\rightarrow {\wp}({\mathbf{B}})$.

Repeatedly apply Proposition \[prop:poly-ac\] with a polymorphism $f$ and $g_1 = \cdots = g_k = h$, each time taking the resulting $g$ and updating $h$ to be $h \cup g$. Note that at each step, the new $h$ is a homomorphism ${\mathbf{A}}\rightarrow {\wp}({\mathbf{B}})$, since the union operation $\cup$ is a polymorphism of ${\wp}({\mathbf{B}})$. When no changes can be made, the resulting $h$ is the desired $h'$.

Let us say that a CSP instance $({\mathbf{A}}, {\mathbf{B}})$ has the *subalgebra SACC* if $({\mathbf{A}}, {\mathbf{B}})$ has the SACC relative to mappings $s, \{ h_{a, b} \}$ such that for all $a \in A$, the set $s(a)$ is a subalgebra, and for all $a, a' \in A$, $b \in s(a)$, the set $h_{a, b}(a')$ is a subalgebra.

\[prop:sacc-implies-subalgebra-sacc\] If a pair $({\mathbf{A}}, {\mathbf{B}})$ of similar structures has the SACC, and all polymorphisms of ${\mathbf{B}}$ are idempotent, then it has the subalgebra SACC.

Suppose that $({\mathbf{A}}, {\mathbf{B}})$ has the SACC with respect to the mappings $s, \{ h_{a, b} \}$. Set $s'(a) = {\langle}s(a) {\rangle}$ for all $a \in A$, and $h'_{a, b}(a') = {\langle}h_{a, b}(a') {\rangle}$ for all $a, a' \in A$, $b \in s(a)$. Clearly, for all such $a, a', b$ we have $h'_{a, b}(a') \subseteq s'(a')$, and also, that $h'_{a, b}$ is a homomorphism ${\mathbf{A}}\rightarrow {\wp}({\mathbf{B}})$ (by Proposition \[prop:subalgebra-ac\]). Let $b$ be an element in $s'(a) \setminus s(a)$ for some $a \in A$. We need to show that there exists a homomorphism $h'_{a, b}$ that satisfies the two conditions of Definition \[def:sacc\] with respect to $s'$, and that also satisfies the subalgebra condition. As $s'(a)$ is defined as ${\langle}s(a) {\rangle}$, it holds that $s'(a) = \{ f(b_1, \ldots, b_k) ~|~ f \mbox{ a polymorphism of } {\mathbf{B}}; b_1, \ldots, b_k \in s(a) \}$; the containment $\supseteq$ is clear by definition of subalgebra, and the containment $\subseteq$ follows from the fact that the right hand side is a subalgebra, which in turn follows from the fact that the set of polymorphisms of ${\mathbf{B}}$ forms a clone and is closed under composition [@szendrei86-clones]. Thus, there exists a polymorphism $f$ of $B$ and elements $b_1, \ldots, b_k \in s(a)$ such that $b = f(b_1, \ldots, b_k)$. Let $g'_{a, b}$ be the homomorphism obtained from Proposition \[prop:poly-ac\] with $g_i = h_{a, b_i}$ and $f$. Set $h'_{a, b}(a') = {\langle}g'_{a, b}(a') {\rangle}$ for all $a' \in A$. The homomorphism $h'_{a, b}$ has the desired properties.

We now turn to prove our tractability result. We will now use the term subalgebra to refer to a *subalgebra* of a 2-semilattice $(B, {\star})$, that is, a subset of $B$ preserved by ${\star}$. Note, however, that we will be working with a relational structure ${\mathbf{B}}$ assumed to have ${\star}$ as a polymorphism, so a subalgebra in the previous sense (that is, with respect to ${\mathbf{B}}$) will also be a subalgebra in this sense. An algebra $(B, {\star})$ having a binary operation is *conservative* if for all $b, b' \in B$, it holds that $b {\star}b' \in \{ b, b' \}$. The following is the statement of our tractability result.

\[thm:twosem-sac\] Let $(B, {\star})$ be a conservative 2-semilattice such that every strongly connected subalgebra is simple. If ${\mathbf{B}}$ is a structure having ${\star}$ as a polymorphism, then singleton arc consistency solves ${{\mathsf{CSP}}}({\mathbf{B}})$.

\[ex:twosem\] We consider the binary operation ${*}$ on $\{ 0, 1, 2, 3 \}$ defined by the following table.

$
\begin{tabular}{|c|c|c|c|c|}
\hline
{*}&  0 & 1 & 2 & 3 \\  \hline
0 &       0 & 1 & 2 & 3 \\ \hline
1 &       1 & 1 & 2  & 1   \\ \hline
2 &       2 & 2  & 2 &  3  \\ \hline
3 &       3 & 1 &  3 & 3 \\ \hline
\end{tabular}
$

It is straightforward to verify that this operation is commutative and conservative, and is a 2-semilattice. The graph induced by this operation has edges $(0, 1), (0, 2), (0, 3), (1, 2), (2, 3), (3, 1)$, as well as self-edges on each of the vertices. There is thus just one strongly connected component of size strictly greater than one, namely, the component $\{ 1, 2, 3 \}$. This is a subalgebra of the algebra $(\{ 0, 1, 2, 3 \}, {*})$ and is readily verified to be simple. Hence, the tractability via singleton arc consistency of any structure preserved by the operation ${*}$ follows from Theorem \[thm:twosem-sac\].

We will make use of the following results. For our purposes here, a *subdirect product* of algebras ${\mathbb{A}}_1, \ldots, {\mathbb{A}}_k$ is a subalgebra $S$ of $A_1 \times \cdots \times A_k$ such that for each $i \in [k]$, it holds that $\pi_i S = A_i$.

\[lemma:subdir-scc\] Suppose that $S$ is a subdirect product of 2-semilattices $S_1, \ldots, S_n$. Then $S \cap ({\overline{S_1}} \times \cdots \times {\overline{S_n}})$ is a subdirect product of ${\overline{S_1}}, \ldots, {\overline{S_n}}$.

Immediate from [@twosemilattices Lemma 3.2].

\[def:almost-trivial\] A relation $S \subseteq B^n$ is *almost trivial* if there exists a partition $I_1, \ldots, I_k$ of $[n]$ such that

-   $t \in S$ if and only if for all $i \in [k]$, it holds that ${\pi}_{I_i} t \in {\pi}_{I_i} S$; and,

-   for each $j \in [k]$, it holds that ${\pi}_{I_j} S$ has the form $\{ (\pi_1(p), \pi_2(p), \ldots, \pi_m(p)) ~|~ p \in [q] \}$ for some $q \geq 1$ and where each mapping $\pi_i$ is a bijection from $[q]$ to a subset of $B$.

\[prop:subdir-of-simple-sc\] A subdirect product of simple strongly connected 2-semilattices is an almost trivial relation, and is hence itself strongly connected.

Immediate from [@twosemilattices Proposition 3.1].

\[prop:sacc-almost-trivial\] Let $({\mathbf{A}}, {\mathbf{B}})$ be an instance that has the SACC with respect to $s: A \rightarrow {\wp}({\mathbf{B}}) \setminus \{ \emptyset \}$. If for each tuple $(a_1, \ldots, a_k) \in R^{{\mathbf{A}}}$, it holds that $R^{{\mathbf{B}}} \cap (s(a_1) \times \cdots \times s(a_k))$ is almost trivial, then there is a homomorphism from ${\mathbf{A}}$ to ${\mathbf{B}}$.

Consider the following graph $G=(A,E)$, where $\{a,b\}\in E$ if and only if there is a relation $R^{\mathbf{A}}$ in ${\mathbf{A}}$, and, if $I_1,\dots,I_k$ is its partition regarding almost triviality of $R^{{\mathbf{B}}} \cap (s(a_1) \times \cdots \times s(a_k))$, there further is an $l\in [k]$ and a tuple $(a_1,\dots,a_m)\in R^{{\mathbf{A}}}_{I_l}$ such that there are $i,j$ with $a=a_i$ and $b=a_j$. For each connected component $C$ of the graph $G$ arbitarily choose $a\in C$ and $b\in s(a)$. Since arc consistency can be established when $a$ is set to $b$ and using the structure of the projected relations $R^{\mathbf{B}}_{I_l}$, there exists a unique extension of $a\mapsto b$ to a homomorphism on $C$. Because of the first property of Definition \[def:almost-trivial\] the homomorphisms on the single components can be combined to a homomorphism on ${\mathbf{A}}$.

The following is the main result used to prove Theorem \[thm:twosem-sac\].

\[thm:sacc-on-max-components\] Suppose that ${\mathbf{B}}$ satisfies the hypotheses of Theorem \[thm:twosem-sac\], and suppose that $({\mathbf{A}}, {\mathbf{B}})$ has the subalgebra SACC via $s: A \rightarrow {\wp}(B) \setminus \{ \emptyset \}$. Then, $({\mathbf{A}}, {\mathbf{B}})$ has the SACC via the map $s': A \rightarrow {\wp}({\mathbf{B}}) \setminus \{ \emptyset \}$ defined by $s'(a) = {\overline{s(a)}}$ for all $a \in A$.

Let $a \in A$ and $b \in {\overline{s(a)}}$. By hypothesis, there exists a homomorphism $h: {\mathbf{A}}\rightarrow {\wp}({\mathbf{B}})$ where $h(a) = \{ b \}$ and for all $a' \in A$, it holds that $h(a') \subseteq s(a')$. We want to show that there exists a homomorphism $h': {\mathbf{A}}\rightarrow {\wp}({\mathbf{B}})$ where $h'(a) = \{ b \}$ and for all $a' \in A$, it holds that $h'(a') \subseteq s'(a')$. Define $h'(a)$ as ${\overline{h(a)}}$ if $h(a) \cap s'(a) \neq \emptyset$, and as $s'(a)$ otherwise. Observe that in the first case, we have $h'(a) = {\overline{h(a)}} \subseteq s'(a)$, and that in both cases, the subset $h'(a)$ is a subalgebra.

We claim that $h'$ is a homomorphism from ${\mathbf{A}}$ to ${\wp}({\mathbf{B}})$. Let $a \in R^{{\mathbf{A}}}$ be a tuple in ${\mathbf{A}}$. For the sake of notation, we assume that $a = (a_1, \ldots, a_{k+l})$, $I = \{ 1, \ldots, k \}$, $J = \{ k+1, \ldots, k+l \}$, and that $I$ contains exactly the coordinates $i \in [k+l]$ such that $h(a_i) \cap s'(a_i) \neq \emptyset$, so that $h'(a_i) = {\overline{h(a_i)}}$ for all $i \in I$ and $h'(a_j) = s'(a_j)$ for all $j \in J$. Let ${T = ({\pi}_I R^{{\mathbf{B}}} \cap (s(a_1) \times \cdots \times s(a_k))) \cap ({\overline{s(a_1)}} \times \cdots \times {\overline{s(a_k)}})}$. By Lemma \[lemma:subdir-scc\], we have that relation $T$ is a subdirect product of ${\overline{s(a_1)}}, \ldots, {\overline{s(a_k)}}$. Further, let $W = {   (R^{{\mathbf{B}}} \cap (s(a_1) \times \cdots \times s(a_{k+l}))) \cap ({\overline{s(a_1)}} \times \cdots \times {\overline{s(a_{k+l})}})   }$. By Lemma \[lemma:subdir-scc\], we have that $W$ is a subdirect product of ${\overline{s(a_1)}}, \ldots, {\overline{s(a_{k+l})}}$. Clearly, ${\pi}_I W \subseteq T$. We show that $T \subseteq {\pi}_I W$ (and hence that $T = {\pi}_I W$), as follows. Let $t$ be a tuple in $T$. Let $w$ be a tuple in $W$ (such a tuple can be obtained, for instance, by ${\star}$-multiplying together all tuples of $R^{{\mathbf{B}}}\cap (s(a_1) \times \cdots \times s(a_{k+l}))$, in any order). By our assumption on ${\mathbf{B}}$ and by Proposition \[prop:subdir-of-simple-sc\], there is a sequence of tuples $u_1, \ldots, u_m$ in $T$ such that ${\pi}_I w \leq u_1 \leq \cdots \leq u_m = t$. We hence have tuples $v_1, \ldots, v_m$ with $v_i \in R^{{\mathbf{B}}}\cap (s(a_1) \times \cdots \times s(a_{k+l}))$ and ${\pi}_I v_i = u_i$ for each $i \in [m]$. The product $(\cdots ((w {\star}v_1) {\star}v_2) {\star}\cdots {\star}v_m)$ gives a tuple in $W$ whose projection onto $I$ is $t$.

By Proposition \[prop:subdir-of-simple-sc\], it holds that $W$ is almost trivial with respect to a partition $\{ I_i \}$. Remove from the $I_i$ any coordinates $l$ such that $s'(a_l)$ has just one element. We now show that the resulting partition $\{ I_i \}$ has the property that each $I_i$ is a subset of either $I$ or $J$. By the homomorphism $h$ and its subalgebra property, there exists a tuple $(t, x) \in R^{{\mathbf{B}}}$ such that $t \in T$ and $x_j \notin {\overline{s(a_j)}}$ for all $j \in J$ (just multiply all tuples in $R^{\mathbf{B}}\cap (h(a_1) \times \cdots \times h(a_{k+l}))$). By the fact that $T \subseteq {\pi}_I W$, we have a tuple $(t, u) \in W$. By the strong connectedness of $W$ (Proposition \[prop:subdir-of-simple-sc\]), there is a tuple $(t', u') \in W$ that is distinct from $(t, u)$ at each coordinate in $\cup I_i$ and such that $(t', u') {\star}(t, u) = (t, u)$. We also have $(t', u') {\star}(t, x) = (t, u')$; note that $u' {\star}x = u'$ by conservativity of ${\star}$. As $u$ and $u'$ differ at every coordinate in $J\cap(\cup I_i)$, the claim follows.

As a consequence of this last result, for any tuple $t \in {\pi}_I W$ and any tuple $u \in {\pi}_J W$, it holds that $(t, u) \in W$. Further it holds that $({\pi}_I R^{{\mathbf{B}}}\cap (h(a_1) \times \cdots \times h(a_k)))\cap (h'(a_1) \times \cdots \times h'(a_k))$ is a subdirect product of $h'(a_1), \ldots, h'(a_k)$ (Lemma \[lemma:subdir-scc\]), and we have that $h'$ is a homomorphism from ${\mathbf{A}}$ to ${\wp}({\mathbf{B}})$.

(Theorem \[thm:twosem-sac\]) Suppose that $({\mathbf{A}}, {\mathbf{B}})$ has the SACC. By Proposition \[prop:sacc-implies-subalgebra-sacc\], the instance $({\mathbf{A}}, {\mathbf{B}})$ has the subalgebra SACC. By Theorem \[thm:sacc-on-max-components\], $({\mathbf{A}}, {\mathbf{B}})$ has the SACC via a mapping $s'$ where for all $a \in A$, it holds that $s'(a)$ is a strongly connected subalgebra. By assumption, each such $s'(a)$ is simple, and it follows from Propositions \[prop:subdir-of-simple-sc\] and \[prop:sacc-almost-trivial\] that there is a homomorphism from ${\mathbf{A}}$ to ${\mathbf{B}}$.

Discussion
==========

In this work, we performed a systematic study of arc consistency and three simple, natural extensions thereof. We performed a comparison of the studied consistency notions based on constraint languages, and proved positive tractability results for singleton arc consistency.

Atserias and Weyer [@atserias-weyer] gave a uniform treatment of AC, PAC, SAC, and general consistency. Among other results, they show that it can be decided, given a constraint language and any pair of the previous consistency methods, whether it is true that the set of instances that passes one of the consistency tests coincides with the set of instances that passes the other. Their results combined with the fact that general consistency/bounded width is decidable [@bkbw] implies that it can be decided whether or not a given constraint language is solvable by any of the other methods.

We conclude by posing one question for future work. Barto and Kozik [@bkbw] have recently characterized all languages solvable by bounded width. Can all such languages be solvable by singleton arc consistency, or are there bounded width languages not solvable by singleton arc consistency? Resolving this question in the positive would seem to yield an interesting alternative characterization of the bounded width languages.

#### Acknowledgements.

The authors thank Manuel Bodirsky for his comments and collaboration. The authors also thank Johan Thapper for his many useful comments.

[^1]: Chen is supported by the Spanish program “Ramon y Cajal”.

[^2]: Both Chen and Dalmau are supported by MICINN grant TIN2010-20967-C04-02.

[^3]: Work by Grußien was supported by the Deutsche Forschungsgemeinschaft (DFG) within the research training group “Methods for Discrete Structures” (GrK 1408).
