$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 