AC-3 (source code)
= AC-3
{c}
= AC3
{c}
{synonym}
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+ed^3)$. Fixed $d$, including two-valued <constraint domains>, gives linear time in $v+e$.
Back to article page
