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 decompositio n methods. We then introduce a new class of tractable CSPs based on the con cept of hypertree decomposition recently developed in Database Theory, and analyze the cost of solving CSPs having bounded hypertree-width. We provide a framework for comparing parametric decomposition-based methods according to tractability criteria and compare the most relevant methods. We show th at the method of hypertree decomposition dominates the others in the case o f general CSPs (i.e., CSPs of unbounded arity), We also make comparisons fo r the restricted case of binary CSPs, Finally, we consider the application of decomposition methods to the dual graph of a hypergraph. In fact, this t echnique is often used to exploit binary decomposition methods for nonbinar y CSPs. However, even in this case, the hypertree-decomposition method turn s out to be the most general method. (C) 2000 Elsevier Science B.V. All rig hts reserved.