Arc consistency

Arc consistency (also called domain consistency or hyper-arc consistency) is a local consistency condition in constraint satisfaction problems that ensures every value in a variable's domain has at least one compatible value in the domain of every variable connected to it by a constraint. If a value has no supporting partner in a neighboring domain, it is eliminated — not because the value is globally impossible, but because it is locally unsupported. Arc consistency is the bridge between local inference and global solvability: it prunes the search space by reasoning about pairs of variables before any search begins.

The concept was formalized in the 1970s by Alan Mackworth, who recognized that many constraint networks could be simplified by enforcing pairwise consistency before attempting full search. The insight is elegant: a constraint between two variables is a relation, and arc consistency requires that for every value on one side of the relation, there exists at least one value on the other side. If no such value exists, the original value cannot participate in any solution and can be safely discarded. This is not a solution; it is a filter, and the filtered problem is closer to the solution set than the original.

The AC-3 Algorithm

The AC-3 algorithm (Arc Consistency 3) is the classic method for enforcing arc consistency. It maintains a queue of constraints (arcs) to be checked. For each arc, the algorithm examines every value in the domain of the first variable and checks whether there exists a compatible value in the domain of the second variable. If a value is unsupported, it is removed from the domain. If any values are removed, all constraints connected to the modified variable are re-added to the queue, because the removal may have eliminated support for values in other variables' domains.

The algorithm converges when the queue is empty, at which point the constraint network is arc-consistent. The worst-case time complexity is O(ed³), where e is the number of constraints and d is the maximum domain size. In practice, AC-3 is often faster because early domain reductions eliminate many values before they are extensively checked. The space complexity is O(e), for the queue and the constraint graph representation.

AC-3 is not the only algorithm for arc consistency. AC-4 achieves O(ed²) time by precomputing support counts, but at higher space cost. AC-2001 and its variants use sophisticated data structures to achieve the same worst-case bound as AC-4 with lower overhead. The choice of algorithm is an engineering trade-off between time, space, and implementation complexity.

Arc Consistency and Search

Arc consistency is almost never sufficient to solve a constraint problem by itself. It is a preprocessing step, a way to shrink the domains before the solver begins its search. But the interaction between arc consistency and search is the architecture of modern constraint solvers. The solver enforces arc consistency, makes a tentative assignment, enforces arc consistency again, and repeats. When a contradiction is found, the solver backtracks, and arc consistency propagates the consequences of the backtrack.

This hybrid architecture — maintaining arc consistency (MAC) — is the dominant strategy in constraint programming. The solver does not merely run AC-3 once at the beginning; it runs a constraint propagation algorithm (often AC-3 or a more sophisticated variant) after every assignment, keeping the constraint network in a state where every remaining value is locally supported. The cost is higher per node, but the pruning is so effective that the total number of nodes explored is dramatically reduced.

Compared to forward checking, arc consistency is stronger but more expensive. Forward checking only checks constraints involving the most recently assigned variable; arc consistency checks all constraints involving any variable whose domain has been reduced. The trade-off is the central question in constraint solver design: how much local reasoning to invest before branching. The empirical answer depends on the problem structure, but the theoretical answer is that arc consistency is worth the cost when the constraint network is sparse and the domains are large — precisely the conditions where unsupported values are most likely to exist.

Beyond Arc Consistency: Path Consistency and Generalizations

Arc consistency is the first level in a hierarchy of local consistencies. Path consistency extends the reasoning to triples of variables: for every pair of values that satisfies the constraint between variables A and B, and every value that satisfies the constraint between B and C, there must exist a value for C that satisfies the constraint between A and C. Path consistency is stronger than arc consistency but exponentially more expensive, and it is rarely used in practice except for small networks or specific problem classes.

Higher-order consistencies — k-consistency, strong k-consistency, and generalized arc consistency for non-binary constraints — extend the reasoning to larger tuples. The general principle is that stronger consistency eliminates more of the search space but requires more computation to enforce. The engineering challenge is to find the right consistency level for the problem at hand, and to enforce it selectively in regions of the search space where it is most needed.

Arc Consistency as a Systems Pattern

Arc consistency is not merely an algorithmic technique; it is a structural pattern for how systems maintain coherence between coupled components. In a distributed system, each node's local state must be consistent with the states of its neighbors; arc consistency is the local check that ensures no node is in a state that its neighbors cannot support. In a market, each price must be supportable by supply and demand conditions; prices that are locally unsupported are eliminated by arbitrage. In a neural network, each neuron's activation must be consistent with the activations of its connected neighbors; the propagation of inhibition and excitation is, at an abstract level, arc consistency in a biological constraint network.

The pattern is universal: local support is a necessary condition for global consistency, and enforcing it prunes impossible states before they are ever explored. The constraint satisfaction solver, the distributed system, and the market all share the same architecture: check local consistency, propagate the consequences, and search only where the local constraints do not already determine the answer.

Arc consistency is the most elegant idea in constraint satisfaction: that the hardest part of solving a problem is not the search, but the elimination of what cannot be true. A solver that does not exploit this principle is not a solver; it is a generator with a validation step. The systems that scale — whether computational, economic, or biological — are the ones that enforce local consistency so aggressively that the remaining search space is small enough to explore.