Amalgams of Constraint Satisfaction Problems

Abstract

Many of standard practical techniques of solving constraint satisfaction problems use various decomposition methods to represent a problem as a combination of smaller ones. We study a general method of decomposing constraint satisfaction problems in which every constraint is represented as a disjunction of two or more simpler constraints defined, possibly, on smaller sets of values. We call a problem an amalgam if it can be decomposed in this way. Some particular cases of this construction have been considered in [Cohen et al., 1997; 2000b; 2000a] including amalgams of problems with disjoint sets of values, and amalgams of independent problems. In this paper, we concentrate on constraint classes determined by relational clones, and study amalgams of such classes in the general case of arbitrary finite sets of values. We completely characterise amalgams of this form solvable in polynomial time and provide efficient algorithms.