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, - and strong -consistency, and prove that the arc-consistency closure is unique.
- Explain how AC-4 and AC-2001 improve AC-3's to the optimal .
- Prove Freuder's backtrack-free theorem and derive the algorithm for tree-structured CSPs.
- Bound cutset conditioning and tree-decomposition methods, and .
- State Schaefer's theorem and the Bulatov–Zhuk dichotomy theorem, and identify what remains open.
A hierarchy of local consistency
If and are arc-consistent sub-domains, so is their componentwise union: a value of keeps its support in . Hence the union of all arc-consistent sub-domains is the largest one:
No deletion removes a value of . By induction the current domains contain , so a value still has its support whenever its arc is revised:
The procedure stops only when no value is unsupported, at an arc-consistent sub-domain containing , which by maximality is . A solution, read as singleton domains, is arc-consistent, so it lies inside : propagation is sound. ∎
Arc consistency is necessary for a solution, far from sufficient. Three mutually adjacent regions with domains are arc-consistent, since each color has the other as support, yet no coloring exists. Path consistency catches this: no pair on two of the regions extends to the third.
Three regions are pairwise adjacent, each with domain {red, green}. What does AC-3 do?
- It empties a domain and reports that no coloring exists
- It removes nothing: every value has a support, although no coloring exists
- It removes one color from each region, leaving a solution
- 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 revisions of 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:
Order each domain. For every arc and value , store , the support found last time. On revision, keep it if it is still in ; otherwise resume the search after it, never before:
Skipping the earlier values is safe: they were already found not to support , and values only ever leave domains. So each pointer advances at most times over the whole run, and there are pointers:
Each arc is still revised times, and each revision spends checking the stored pointers: another . Space is one pointer per arc and value:
Nothing does better in the worst case: just verifying that every arc is consistent may require looking at all value pairs of all constraints.
Global constraints get dedicated propagators. For , GAC is a matching problem: value survives in iff the edge 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 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
Suppose have been assigned consistently and is next. At most of its neighbors precede it; call them :
Their values form a consistent assignment to variables, and strong -consistency includes -consistency, so it extends to :
In a binary CSP the only constraints between and earlier variables are those edges, so is consistent with the whole partial assignment. Induction on finishes the proof. ∎
The catch: enforcing -consistency for 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:
Pick a root and order the variables so that every parent precedes its children (width 1):
Upward pass: for down to , call REVISE, deleting the parent's values that have no support in the child. If a domain empties, there is no solution.
Children are processed before their parents, so 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:
Downward pass: give any value, then each a value supporting its parent's. One always exists, so this pass takes and never backtracks.
A tree-structured CSP has variables with values each. At most how many value-pair checks does the upward pass make?
Show the answer
99900 checks
One REVISE per edge: edges, each comparing at most value pairs, so checks. Brute force would face 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 of variables leaves a forest, enumerate the assignments to , prune the other domains accordingly and solve the forest: 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 if bags have at most 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 , the set of relations allowed in constraints, and asks how hard is for arbitrary shapes.
Local consistency has its own exact characterization. Barto and Kozik (2014) determined which languages are decided by enforcing strong -consistency for some fixed ("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 ). The arc-consistency closure is unique, independent of revision order, and contains every solution.
- AC-3 costs ; AC-4 and AC-2001 reach the optimal , and global constraints such as Alldiff get stronger, matching-based propagators.
- Freuder: strong -consistency plus an ordering of width below gives backtrack-free search. Trees (width 1) need only directional arc consistency, hence .
- Near-trees yield to cutset conditioning, , or tree decomposition, ; 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 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.
Two arc-consistency algorithms revise the arcs of the same CSP in different orders. What can you say about the domains they end with?
- They are identical: both compute the unique largest arc-consistent sub-domain
- They may differ, though both are arc-consistent
- The algorithm that performs more revisions ends with smaller domains
- 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 , and both algorithms stop at an arc-consistent sub-domain containing , which by maximality is itself.
Which algorithm enforces arc consistency in time with only extra space?
- AC-3
- AC-4
- PC-2
- 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 time with one pointer per arc and value.
Why does directional arc consistency make a tree-structured CSP backtrack-free?
- Because trees have very few solutions
- 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
- Because AC-3 is exponential only on graphs with cycles
- 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.
Which Boolean constraint language is not one of Schaefer's tractable classes?
- Horn clauses
- 2-CNF clauses
- Linear equations mod 2
- 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).