Refinements and independence

Abstract

The constraint satisfaction problem provides a natural framework for expressing many combinatorial problems. Since the general problem is NP-hard, an important question is how to restrict the problem to ensure tractability. The concept of independence has proven to be a useful method for constructing tractable constraint classes from existing classes. Since checking the independence property may be a difficult task, we provide a simple method for checking this property. Our method builds on a somewhat surprising connection between independence and refinements which is a recently established way of reducing one constraint satisfaction problem to another. Refinements have two interesting properties: (1) they preserve consistency; and (2) their correctness can be easily checked by a computer-assisted analysis. We show that all previous independence results of the point algebra for totally ordered and partially ordered time can be derived using this method. We also employ the method for deriving new tractable classes. Show more