Does DAC choose a final assignment?

No. It establishes a domain-support property; assignment is a separate step.

Can DAC detect impossibility?

Yes, when filtering empties a domain, although it may miss other impossible cases.

Is full arc consistency sufficient for every problem?

No, as the two-color triangle demonstrates.

AI Glossary / Graphs and symbolic AI / Advanced

Directional arc consistency

Definition

Directional arc consistency, or DAC, is a constraint-satisfaction property defined relative to a fixed ordering of variables. For each binary constraint, every retained value of the earlier variable must have at least one compatible value in the later variable's domain. Support in the reverse direction is not required by this property.

What it means

A constraint-satisfaction problem describes variables, their allowed values, and rules restricting which combinations are acceptable. DAC removes some values that cannot be supported by a later connected variable. It is a filtering condition, not generally a certificate that all remaining choices can coexist.
The word directional refers to the chosen ordering, not necessarily to a physical direction or a causal relationship. Reordering the same variables can change which values are removed. Full arc consistency requires support in both directions for each binary constraint and is therefore stronger.

How it works

Choose an ordering and examine variables from its end toward its beginning. For each current variable, revise the domain of every earlier variable connected to it: remove an earlier value if no current-domain value satisfies their shared constraint.
Processing backward allows restrictions on later choices to reach earlier domains. If a domain becomes empty, the original problem has no solution under its current restrictions. If every domain stays nonempty, a general network may still be unsatisfiable.
A useful special case is a tree-structured binary constraint graph. Root the tree and order parents before children. After backward filtering, nonempty domains permit assignments from the root downward without backtracking: each chosen parent value has a compatible child value, and separate subtrees have no extra constraints joining them. Adding a cross-connection can invalidate that reasoning.

Three practical examples

Product configuration: A configurator filters component options against compatible downstream choices. When the relationships form a tree, a suitable order can support straightforward selection. A hidden shared-power constraint between branches must be represented before relying on that structure.
Appointment planning: A scheduler checks whether an earlier appointment time has a compatible later slot. DAC can eliminate unsupported times. Additional room-sharing or staffing rules can connect distant appointments and require further reasoning beyond these pairwise checks.
Symbolic AI preprocessing: A search system narrows variable domains before trying complete assignments. Comparing several orderings can reveal differences in pruning, but a smaller retained domain does not by itself establish faster overall search or a better business outcome.

Think of it this way

Imagine planning a sequence of purchases from the last requirement backward. You remove an earlier option when it leaves no compatible later choice. Keeping an option means it has the required local support; it does not necessarily mean every independently supported choice works together in the final package.

Worked example

Take three variables with integer domains A = {1, 2, 3}, B = {2, 3, 4}, and C = {3}. The only constraints are A less than B and B less than C. Use the ordering A, B, C.
First revise B against C. Because C can only be 3, B = 3 and B = 4 have no support under B less than C. Remove them, leaving B = {2}.
Next revise A against the reduced B domain. Only A = 1 is less than 2, so remove A = 2 and A = 3. The remaining domains are A = {1}, B = {2}, and C = {3}. The assignment (1, 2, 3) satisfies both constraints. Exhaustively checking the original nine combinations also finds this as the sole solution.
Now start again from the original domains but use the reverse ordering C, B, A. Revising B against A removes nothing: B values 2, 3, and 4 each have support at A = 1. Revising C against B removes nothing because C = 3 has support at B = 2. These unchanged domains satisfy DAC for the reversed ordering, despite containing values absent from every complete solution.
Give three variables X, Y, and Z the domain {red, blue} and require every pair to differ. Each color has support in the other variable's domain for every pair, so even full arc consistency removes nothing. Nevertheless, three mutually different colors cannot be selected from two colors. Local support is not general global feasibility.

Illustrative case study

Fictional Cedar Configurations uses backward filtering to simplify a chain of accessory choices. The interface initially calls every surviving option “guaranteed compatible.” That description works only within the structural assumptions behind its selection procedure.
A new product introduces an additional compatibility rule between two previously separate branches. Reviewers construct a small case where local supports remain but cannot be selected together. The team changes the interface to distinguish filtered candidates from verified complete configurations and adds the new rule to the solver.
The improvement comes from aligning the claim with the actual constraints, rather than assuming a familiar preprocessing step proves more than it does.

Common misconceptions and mistakes

“Direction means the constraint only applies one way.” The underlying compatibility rule still applies to a complete assignment.
“Any variable ordering gives identical pruning.” The reversed worked example shows otherwise.
“Nonempty domains prove a solution exists.” Cyclic constraint networks can retain locally supported but globally incompatible values.
“DAC always removes every impossible value.” It can leave values that never occur in a solution.
“Tree reasoning survives any added constraint.” Cross-connections can destroy the required tree structure.

Business use

Record the variable order, domains, and constraints used for filtering. When presenting guaranteed completion without backtracking, verify the tree structure and parent-before-child ordering rather than relying on a diagram that omits operational rules.
For general configuration or scheduling problems, treat DAC as one possible preprocessing step. Measure its filtering cost alongside subsequent search, and validate final assignments against every applicable constraint. A changed domain or new relationship requires renewed analysis.

Check your understanding

Why is B = 4 removed in the first ordering?

Answer: No permitted C value is greater than 4.

Why does the reverse ordering retain B = 4?

Answer: It has support at A = 1 in the required direction.

What breaks the tree guarantee?

Answer: Additional constraints connecting separate branches can introduce cycles.

Related terms

Constraint satisfaction
Domain
Constraint propagation
support
arc consistency
variable ordering
tree-structured CSP
backtracking

Learn next

Implement both orders in the worked example and compare their retained domains with exhaustive solutions. Then test the two-color triangle to separate local consistency from global feasibility.

Local consistency

Sources

AIMA glossary, directional arc consistency: https://github.com/aimacode/aima-glossary/blob/master/glossary.md Christian Bessiere, Constraint Propagation, section 7.1.1: https://www.lirmm.fr/~bessiere/Site/stock/TR06020.pdf UC Berkeley CS188, ordering and tree-structured constraint problems: https://inst.eecs.berkeley.edu/~cs188/textbook/csp/ordering.html

Previous: Directed graph Next: Directional-change intrinsic time