The iterative process of applying constraints in a constraint network to reduce variable domains by eliminating values that cannot be part of any solution, often implemented via arc consistency, forward checking, or generalized consistency algorithms.

Principle

Use local constraint relations to infer and remove impossible values, thereby shrinking domains and exposing forced assignments; repeated application tightens the problem and reduces combinatorial branching.

Demonstration

In a binary CSP with constraint X ≠ Y and domains X = {1,2}, Y = {2,3}, propagation removes 2 from X's domain when Y is fixed to 2, and arc consistency can iteratively remove values until no further changes occur.

Misapplication

Overly aggressive global propagation without regard to cost can waste time on little pruning (high overhead), and naive propagation that ignores dependencies between constraints can produce incorrect domain reductions if implemented incorrectly.

Consequence

Proper constraint propagation substantially reduces search by eliminating infeasible branches early, often turning an intractable search into a tractable one when combined with search heuristics.

Reversal

The reverse is to perform search without any propagation (pure brute-force enumeration of assignments), which is always correct but typically far less efficient due to missing early pruning.

Boundary

Applies to discrete constraint satisfaction problems and combinatorial search; continuous domains require different propagation techniques (interval arithmetic, constraint relaxation) and certain global constraints require specialized propagators.

Semantic Tension

Tension exists between local propagation (arc consistency) and global consistency notions: stronger consistency yields better pruning but at greater computational cost; the trade-off is problem-dependent.

Synthesis

Constraint propagation is the disciplined application of local constraint deductions to prune variable domains incrementally, balancing pruning power against computational cost to make combinatorial search feasible in practice.