Arc consistency

A directed requirement for a binary constraint $R_{ij}$: every remaining $x\in D_i$ has at least one support $y\in D_j$ with $(x,y)\in R_{ij}$. Revising the arc $i\to j$ deletes unsupported values from $D_i$; it does not directly delete values from $D_j$. Full arc consistency requires the condition in both directions on every edge of the constraint graph. On general graphs, it need not imply that a complete solution exists.

Compute an arc-consistency closure by revising every directed constrained pair in complete sweeps until one sweep deletes nothing. The first sweep is unconditional. With $v$ variables, maximum constraint domain size $d$, and $e$ constrained pairs, at most $vd$ deletions permit at most $vd+1$ sweeps. At $O(d^2)$ per revision plus $O(v)$ per emptiness scan, a direct time complexity bound is $O((vd+1)(e{d}^2+v))$. AC-3 uses a work list to avoid scanning unrelated arcs after each local change.

The greatest componentwise subdomains of given finite initial constraint domains satisfying every directed arc consistency condition, allowing empty subdomains. Repeated sound revisions to a fixed point produce this same closure regardless of revision order, provided every affected arc is eventually reconsidered.

For the proof, fix subdomains $E_i$ of the initial $D_i$ satisfying arc consistency. If all current $D_i$ contain $E_i$, every value in $E_i$ has a support in $E_j\subseteq D_j$, so revising $i\to j$ preserves $E_i$. Mathematical induction shows that every revision preserves every such family $E$. At termination the current domains themselves satisfy arc consistency, so they are the greatest such family. Algorithms that stop immediately on the first empty constraint domain need not finish computing the closure, but correctly establish that no complete solution exists.

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$.