Arc Consistency and Friends

The constraint satisfaction problem (CSP) involves deciding, given a set of variables and a set of constraints on the variables, whether or not there is an assignment to the variables satisfying all of the constraints. Cases of the constraint satisfaction problem appear in many fields of study, including artificial intelligence, spatial and temporal reasoning, logic, combinatorics, and algebra. Indeed, the constraint satisfaction problem is flexible in that it admits a number of equivalent formulations. In this paper, we work with the formulation as the relational homomorphism problem: given two similar relational structures A and B, does there exist a homomorphism from A to B? In this formulation, one can view each relation of A as containing variable tuples that are constrained together, and the corresponding relation of B as containing the permissible values for the variable tuples [18]. The constraint satisfaction problem is in general NPhard; this general intractability has motivated the study of restricted versions of the CSP that have various desirable complexity and algorithmic properties.