ArcConsistency

Arc consistency, also known as arc-consistency, is a local consistency condition applied to constraint satisfaction problems (CSPs). In a CSP, variables each have a finite domain of possible values and constraints restrict which combinations of values are allowed. A binary constraint between two variables X and Y is arc consistent if for every value x in the domain of X, there exists some value y in the domain of Y such that the pair (x, y) satisfies the constraint. A CSP is arc-consistent (for all its binary constraints) when every arc between every pair of variables is arc consistent. Arc consistency is a form of constraint propagation used to prune values from variable domains before or during search.

The standard algorithm to enforce arc consistency on binary CSPs is AC-3. It maintains a queue of arcs (variable pairs with a constraint) and repeatedly revises the domain of the first variable to remove values with no support in the second variable. If a value is removed, all arcs entering the affected variable are re-enqueued because they may lose support as well. The worst-case time complexity of AC-3 is O(e d^3), where e is the number of binary constraints and d is the maximum domain size; in practice, performance is often better for sparse graphs and small domains.

Generalizations include Generalized Arc Consistency (GAC) for constraints of arbitrary arity, and directional arc consistency or path consistency. Arc consistency is commonly used as a preprocessing step or during search to reduce the search space; if a domain becomes empty, the CSP is unsatisfiable under the current path, prompting backtracking or more powerful consistency checks.