(PDF) Peter van Beek and Rina Dechter. Constraint tightness versus global consistency. Proceedings of the 4th International Conference on Principles of Knowledge Representation and Reasoning, Bonn, Germany, 572-582, May, 1994.
Constraint networks are a simple representation and reasoning framework with diverse applications. In this paper, we present a new property called constraint tightness that can be used for characterizing the difficulty of problems formulated as constraint networks. Specifically, we show that when the constraints are tight they may require less preprocessing in order to guarantee a backtrack-free solution. This suggests, for example, that many instances of crossword puzzles are relatively easy while scheduling problems involving resource constraints are quite hard. Formally, we present a relationship between the tightness or restrictiveness of the constraints, and the level of local consistency sufficient to ensure global consistency, thus ensuring backtrack-freeness. Two definitions of local consistency are employed. The traditional variable-based notion leads to a condition involving the tightness of the constraints, the level of local consistency, and the arity of the constraints, while a new definition of relational consistency leads to a condition expressed in terms of tightness and local-consistency level, alone. New algorithms for enforcing relational consistency are introduced and analyzed.