Arc Consistency

Arc consistency is a local consistency property in constraint satisfaction that eliminates values from variable domains based on pairwise constraints. A variable is arc-consistent with another if every value in its domain has at least one supporting value in the other's domain — a value that satisfies the binary constraint between them. Enforcing arc consistency prunes the search space before backtracking begins, often revealing that no solution exists without exhaustive search.

The algorithmic appeal of arc consistency is its polynomial-time cost: enforcing it across a CSP with n variables and domain size d requires O(n²d²) time in the worst case. This is cheap relative to the exponential search space it prunes. Yet arc consistency is only one point in a spectrum of propagation strengths — from node consistency (weakest) to path consistency, k-consistency, and global constraints. The choice of propagation level is a systems design decision: stronger propagation removes more infeasible assignments but costs more per node, and the optimal balance depends on constraint graph structure.

The limits of arc consistency are instructive. It guarantees that no solution is eliminated, but it does not guarantee that a solution exists after enforcement. Many CSPs are arc-consistent yet unsatisfiable — the propagation reveals local feasibility while global infeasibility remains hidden. This is the same pattern that appears in distributed systems with local consistency protocols: what holds pairwise may not hold globally.