AC-3

An arc consistency algorithm maintaining a work list of directed constrained variable pairs. Revising $i\to j$ deletes each value of $D_i$ with no compatible value in $D_j$. If $D_i$ shrinks, incoming arcs $k\to i$ are reconsidered; the just-used neighbor $j$ need not be included, since deleted values had no support in $D_j$ and hence supported no surviving value there. Initially empty constraint domains are rejected before processing.

Each deletion preserves every complete solution: a solution using the removed value would supply its missing support. Therefore an empty constraint domain certifies impossibility. Successful termination establishes arc consistency but need not establish satisfiability. A triangle of two-valued inequality constraints supplies a counterexample: all values have pairwise support, but no assignment can satisfy all three inequalities.

For $v$ variables, $e$ constrained pairs and maximum constraint domain size $d$, assume constant-time compatibility tests for combined pair relations. A revision costs $O(d^2)$, and each shrinking source constraint domain can cause at most $d$ rounds of reconsideration of its incoming arcs. Thus there are $O(ed)$ revisions and time complexity $O(v+e{d}^3)$. Fixed $d$, including two-valued constraint domains, gives linear time in $v+e$.