A Comparison of Structural CSP Decomposition Methods
We compare tractable classes of constraint satisfaction problems (CSPs). We first give a uniform presentation of the major structural CSP decomposition methods. We then introduce a new class of tractable CSPs based on the concept of hypertree decomposition recently developed in Database Theory. We introduce a framework for comparing parametric decomposition-based methods according to tractability criteria and compare the most relevant methods. We show that the method of hypertree decomposition dominates the others in the case of general (nonbinary) CSPs. 1 Constraint Satisfaction Problems An instance of a constraint satisfaction problem (CSP) (also constraint network) is a triple I = (V ar; U; C), where V ar is a finite set of variables, U is a finite domain of values, and C = fC 1 ; C 2 ; : : : ; C q g is a finite set of constraints. Each constraint C i is a pair (S i ; r i ), where S i is a list of variables of length m i called the constraint scope, and r i is an m i -...