Simple Algorithm
Artificial Intelligence · Deep Layer · 28 min

Arc Consistency & Propagation

AC-3, path consistency and tree-structured CSPs.

Arc consistency looks at constraints two variables at a time. On some problems it does all the work of search; on others it removes nothing at all. Knowing exactly when local consistency buys global consistency explains why tree-shaped problems are easy, why treewidth governs the cost of every CSP, and what the CSP dichotomy theorem settled in 2017.

What you’ll learn

  • Define node, arc, path, kk- and strong kk-consistency, and prove that the arc-consistency closure is unique.
  • Explain how AC-4 and AC-2001 improve AC-3's O(ed3)\order{ed^3} to the optimal O(ed2)\order{ed^2}.
  • Prove Freuder's backtrack-free theorem and derive the O(nd2)\order{nd^2} algorithm for tree-structured CSPs.
  • Bound cutset conditioning and tree-decomposition methods, O(dc(n−c)d2)\order{d^c(n-c)d^2} and O(ndw+1)\order{nd^{w+1}}.
  • State Schaefer's theorem and the Bulatov–Zhuk dichotomy theorem, and identify what remains open.

A hierarchy of local consistency

DerivationProof
  1. D∗=⋃{D′⊆D: D′ arc-consistent}D^*=\bigcup\big\{D'\subseteq D:\ D'\ \text{arc-consistent}\big\}

    If D′D' and D′′D'' are arc-consistent sub-domains, so is their componentwise union: a value of Di′D'_i keeps its support in Dj′⊆Dj′∪Dj′′D'_j\subseteq D'_j\cup D''_j. Hence the union of all arc-consistent sub-domains is the largest one:

  2. D∗⊆D(t) ⟹ D∗⊆D(t+1)D^*\subseteq D^{(t)}\ \Longrightarrow\ D^*\subseteq D^{(t+1)}

    No deletion removes a value of D∗D^*. By induction the current domains contain D∗D^*, so a value a∈Di∗a\in D^*_i still has its support b∈Dj∗⊆Djb\in D^*_j\subseteq D_j whenever its arc is revised:

  3. D(final) arc-consistent and D∗⊆D(final) ⟹ D(final)=D∗D^{(\mathrm{final})}\ \text{arc-consistent and}\ D^*\subseteq D^{(\mathrm{final})}\ \Longrightarrow\ D^{(\mathrm{final})}=D^*

    The procedure stops only when no value is unsupported, at an arc-consistent sub-domain containing D∗D^*, which by maximality is D∗D^*. A solution, read as singleton domains, is arc-consistent, so it lies inside D∗D^*: propagation is sound. ∎

Arc consistency is necessary for a solution, far from sufficient. Three mutually adjacent regions with domains {r,g}\{r,g\} are arc-consistent, since each color has the other as support, yet no coloring exists. Path consistency catches this: no pair (r,g)(r,g) on two of the regions extends to the third.

Check your understanding

Three regions are pairwise adjacent, each with domain {red, green}. What does AC-3 do?

  1. It empties a domain and reports that no coloring exists
  2. It removes nothing: every value has a support, although no coloring exists
  3. It removes one color from each region, leaving a solution
  4. It cannot run, because the constraint graph has a cycle
Show the answer

B. It removes nothing: every value has a support, although no coloring exists

On every arc, red has green as support and green has red, so AC-3 stops without deleting anything. The inconsistency lives in a triple of variables; strong 3-consistency (path consistency) exposes it.

Optimal arc consistency

AC-3's bound counts O(ed)\order{ed} revisions of O(d2)\order{d^2} checks each. Its waste is that every revision searches for supports from scratch. The optimal algorithms never re-examine a value pair already ruled out:

DerivationWhy AC-2001 runs in O(ed²) time
  1. Last(i,a,j) only moves forward through Dj\mathrm{Last}(i,a,j)\ \text{only moves forward through}\ D_j

    Order each domain. For every arc (Xi,Xj)(X_i,X_j) and value a∈Dia\in D_i, store Last(i,a,j)\mathrm{Last}(i,a,j), the support found last time. On revision, keep it if it is still in DjD_j; otherwise resume the search after it, never before:

  2. ∑arcs (i,j) ∑a∈Di(pointer steps) ≤ 2e⋅d⋅d=O(ed2)\sum_{\text{arcs }(i,j)}\ \sum_{a\in D_i}(\text{pointer steps})\ \le\ 2e\cdot d\cdot d=\order{ed^2}

    Skipping the earlier values is safe: they were already found not to support aa, and values only ever leave domains. So each pointer advances at most dd times over the whole run, and there are 2e⋅d2e\cdot d pointers:

  3. time O(ed2),space O(ed)\text{time}\ \order{ed^2},\qquad\text{space}\ \order{ed}

    Each arc is still revised O(d)\order{d} times, and each revision spends O(d)\order{d} checking the stored pointers: another O(ed2)\order{ed^2}. Space is one pointer per arc and value:

  4. Ω(ed2) constraint checks\Omega(ed^2)\ \text{constraint checks}

    Nothing does better in the worst case: just verifying that every arc is consistent may require looking at all d2d^2 value pairs of all ee constraints.

Global constraints get dedicated propagators. For Alldiff(X1,…,Xk)\mathrm{Alldiff}(X_1,\dots,X_k), GAC is a matching problem: value vv survives in DiD_i iff the edge (Xi,v)(X_i,v) lies in some matching of the variable–value graph that covers every variable. Régin (1994) computes this in polynomial time from one maximum matching plus a search for alternating paths and cycles. The payoff is real: three variables with domains {1,2}\{1,2\} under Alldiff are pairwise arc-consistent, since any two can differ, but GAC sees at once that three variables cannot share two values.

Width, trees and backtrack-free search

DerivationProof
  1. r=∣{neighbors of Xt before Xt}∣ ≤ w ≤ k−1r=\big|\{\text{neighbors of }X_t\text{ before }X_t\}\big|\ \le\ w\ \le\ k-1

    Suppose X1,…,Xt−1X_1,\dots,X_{t-1} have been assigned consistently and XtX_t is next. At most ww of its neighbors precede it; call them Xp1,…,XprX_{p_1},\dots,X_{p_r}:

  2. ∃ v∈Dt:(aps,v)∈Rpstfor s=1,…,r\exists\,v\in D_t:\quad(a_{p_s},v)\in R_{p_s t}\quad\text{for } s=1,\dots,r

    Their values form a consistent assignment to rr variables, and strong kk-consistency includes (r+1)(r+1)-consistency, so it extends to XtX_t:

  3. {X1=a1, …, Xt−1=at−1, Xt=v} consistent\{X_1{=}a_1,\ \dots,\ X_{t-1}{=}a_{t-1},\ X_t{=}v\}\ \text{consistent}

    In a binary CSP the only constraints between XtX_t and earlier variables are those rr edges, so Xt=vX_t=v is consistent with the whole partial assignment. Induction on tt finishes the proof. ∎

The catch: enforcing kk-consistency for k≥3k\ge3 can add new constraints, that is, new edges, which may raise the width, so you cannot always enforce your way below it. Arc consistency never adds edges, which is why trees are the clean case. There even directional arc consistency suffices:

DerivationTree-structured CSPs in O(nd²)
  1. X1=root,pa(Xj) precedes XjX_1=\text{root},\qquad \mathrm{pa}(X_j)\ \text{precedes}\ X_j

    Pick a root and order the variables so that every parent precedes its children (width 1):

  2. (n−1) revisions×O(d2)=O(nd2)(n-1)\ \text{revisions}\times\order{d^2}=\order{nd^2}

    Upward pass: for j=nj=n down to 22, call REVISE(pa(Xj),Xj)(\mathrm{pa}(X_j),X_j), deleting the parent's values that have no support in the child. If a domain empties, there is no solution.

  3. ∀a∈Dpa(j)  ∃ b∈Dj: (a,b)∈Rpa(j), j\forall a\in D_{\mathrm{pa}(j)}\ \ \exists\, b\in D_j:\ (a,b)\in R_{\mathrm{pa}(j),\,j}

    Children are processed before their parents, so DjD_j is already final when it is used to revise its parent. Every value left in a parent therefore has a support in each child's final domain:

  4. total: O(nd2) time, no backtracking\text{total: }\order{nd^2}\ \text{time, no backtracking}

    Downward pass: give X1X_1 any value, then each XjX_j a value supporting its parent's. One always exists, so this pass takes O(nd)\order{nd} and never backtracks.

Predict before you look

A tree-structured CSP has n=1,000n=1{,}000 variables with d=10d=10 values each. At most how many value-pair checks does the upward pass make?

Show the answer

99900 checks

One REVISE per edge: n−1=999n-1=999 edges, each comparing at most d2=100d^2=100 value pairs, so 99,90099{,}900 checks. Brute force would face 10100010^{1000} complete assignments.

Treewidth, cutsets and the complexity frontier

Most constraint graphs are not trees, but many are close to one. Two standard ways to exploit that:

  • Cycle cutset conditioning. If deleting a set SS of cc variables leaves a forest, enumerate the dcd^c assignments to SS, prune the other domains accordingly and solve the forest: O(dc (n−c) d2)\order{d^c\,(n-c)\,d^2} in total. Finding a minimum cutset is the NP-hard feedback-vertex-set problem, but good approximations exist.
  • Tree decomposition. Cover the variables with bags arranged in a tree so that every constraint's scope lies inside some bag and the bags containing any one variable form a connected subtree. Treat each bag as a mega-variable whose values are the consistent assignments to it, at most dw+1d^{w+1} if bags have at most w+1w+1 variables; adjacent bags must agree on shared variables. The result is a tree-structured CSP.

Structural results restrict the shape of the constraint graph. The other axis restricts the constraint language Γ\Gamma, the set of relations allowed in constraints, and asks how hard CSP(Γ)\mathrm{CSP}(\Gamma) is for arbitrary shapes.

Local consistency has its own exact characterization. Barto and Kozik (2014) determined which languages are decided by enforcing strong kk-consistency for some fixed kk ("bounded width"), confirming another Feder–Vardi conjecture. Linear equations mod 2 are the archetypal language that is tractable yet beyond every fixed level of local consistency: it takes Gaussian elimination.

Key takeaways

  • Local consistency forms a hierarchy (node, arc, path, strong kk). The arc-consistency closure is unique, independent of revision order, and contains every solution.
  • AC-3 costs O(ed3)\order{ed^3}; AC-4 and AC-2001 reach the optimal O(ed2)\order{ed^2}, and global constraints such as Alldiff get stronger, matching-based propagators.
  • Freuder: strong kk-consistency plus an ordering of width below kk gives backtrack-free search. Trees (width 1) need only directional arc consistency, hence O(nd2)\order{nd^2}.
  • Near-trees yield to cutset conditioning, O(dc(n−c)d2)\order{d^c(n-c)d^2}, or tree decomposition, O(ndw+1)\order{nd^{w+1}}; under ETH, treewidth is essentially the right parameter.
  • On the language side, Schaefer's Boolean dichotomy (1978) grew into the Bulatov–Zhuk theorem (2017): every finite-domain CSP(Γ)\mathrm{CSP}(\Gamma) is in P or NP-complete.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

Two arc-consistency algorithms revise the arcs of the same CSP in different orders. What can you say about the domains they end with?

  1. They are identical: both compute the unique largest arc-consistent sub-domain
  2. They may differ, though both are arc-consistent
  3. The algorithm that performs more revisions ends with smaller domains
  4. They are identical only if the constraint graph is a tree
Show the answer

A. They are identical: both compute the unique largest arc-consistent sub-domain

Deleting unsupported values never removes anything in D∗D^*, and both algorithms stop at an arc-consistent sub-domain containing D∗D^*, which by maximality is D∗D^* itself.

Question 2

Which algorithm enforces arc consistency in O(ed2)\order{ed^2} time with only O(ed)\order{ed} extra space?

  1. AC-3
  2. AC-4
  3. PC-2
  4. AC-2001 (AC-3.1)
Show the answer

D. AC-2001 (AC-3.1)

AC-2001 keeps AC-3's queue but remembers, for every arc and value, the last support found and resumes from it. Pointers only move forward, which gives O(ed2)\order{ed^2} time with one pointer per arc and value.

Question 3

Why does directional arc consistency make a tree-structured CSP backtrack-free?

  1. Because trees have very few solutions
  2. Because in a root-first order each variable has one earlier neighbor, its parent, and every parent value left has a support in the child
  3. Because AC-3 is exponential only on graphs with cycles
  4. Because MRV always assigns the root first
Show the answer

B. Because in a root-first order each variable has one earlier neighbor, its parent, and every parent value left has a support in the child

This is Freuder's theorem with width 1 and strong 2-consistency: the only constraint between a new variable and the assigned ones is the edge to its parent, and that edge is guaranteed a support.

Question 4

Which Boolean constraint language is not one of Schaefer's tractable classes?

  1. Horn clauses
  2. 2-CNF clauses
  3. Linear equations mod 2
  4. 3-CNF clauses
Show the answer

D. 3-CNF clauses

Clauses of three literals give 3-SAT, which is NP-complete. Horn clauses (unit propagation), 2-CNF (implication graph) and affine relations (Gaussian elimination) are all tractable.

Further reading

  • A. K. Mackworth, "Consistency in networks of relations," Artificial Intelligence 8(1) (1977), 99–118.
  • E. C. Freuder, "A sufficient condition for backtrack-free search," Journal of the ACM 29(1) (1982), 24–32.
  • C. Bessière, J.-C. Régin, R. H. C. Yap & Y. Zhang, "An optimal coarse-grained arc consistency algorithm," Artificial Intelligence 165(2) (2005), 165–185.
  • R. Dechter, Constraint Processing (Morgan Kaufmann, 2003).
  • A. A. Bulatov, "A dichotomy theorem for nonuniform CSPs," FOCS (2017); D. Zhuk, "A proof of the CSP dichotomy conjecture," Journal of the ACM 67(5) (2020).