Tech Report CS-90-36

Efficient Arc Consistency Algorithm for a Class of CSP Problems

Yves Deville and Pascal Van Hentenryck

December 1990

Abstract:

Consistency techniques have been studied extensively in the past as a way of tackling constraint satisfaction problems (CSP). In particular, various arc consistency algorithms have been proposed, originating from Waltz' filtering algorithm and culminating in the optimal algorithm AC-4 of Mohr and Henderson. AC-4 runs in $O(ed ^ 2 )$ in the worst case, where $e$ is the number of arcs (or constraints) and $d$ is the size of the largest domain. Being applicable to the whole class of (binary) CSP, these algorithms do not take into account the semantics of constraints.

In this paper, we present a new generic arc consistency algorithm AC-5. The algorithm is parametrized on two specified procedures and it can be instantiated to reduce to AC-3 and AC-4. More important, AC-5 can be instantiated to produce an $O(ed)$ algorithm for two important classes of constraints: functional and monotonic constraints. We also show that AC-5 has an important application in constraint logic programming over finite domains. The kernel of the constraint-solver for such a programming language is an arc consistency algorithm for a set of basic constraints. We prove that AC-5, in conjunction with node consistency, provides a decision procedure for these constraints running in time $O(ed)$.

(complete text in pdf)