Many combinatorial search problems can be expressed as

constraint satisfaction problems

, and this class of problems is known to be NP-complete in general. In this paper we investigate

disjunctive constraints

, that is, constraints which have the form of the disjunction of two constraints of specified types. We show that when the constraint types involved in the disjunction have a certain property, which we call

independence

, and when a certain restricted class of problems is tractable, then the class of all problems involving these disjunctive constraints is tractable. We give examples to show that many known examples of tractable constraint classes arise in this way, and derive new tractable classes which have not previously been identified.
Keywords Constraint satisfaction problem - complexity - NP-completeness