Building tractable disjunctive constraints

Many combinatorial search problems can be expressed as 'constraint satisfac tion problems'. This class of problems is known to be NP-hard in general, b ut a number of restricted constraint classes have been identified which ens ure tractability. This paper presents the first general results on combinin g tractable constraint classes to obtain larger, more general, tractable cl asses. We give examples to show that many known examples of tractable const raint classes, from a wide variety of different contexts, can be constructe d from simpler tractable classes using a general method. We also construct several new tractable classes that have not previously been identified.