As in Waltz filtering, constraint propagation can greatly reduce the size of a CSP search:

- Initialize nodes to sets of all values in their respective domains.
- When the possible values of a node constrain the possible values
of its neighbors, remove impossible values from the sets for the neighbors.
An arc

*(X, Y)*is*arc-consistent*if for every value*x &isin X*, there is some value*y &isin Y*that satisfies the constraint represented by the arc.*k-consistency*follows multiple arcs to check for consistency (arc consistency is 2-consistency).

Some search may be left after constraint propagation, but the amount of search can be greatly reduced.

For scheduling problems, possible value sets can be represented as
ranges *[ min, max ]*; constraints can allow the range limits to be
reduced.