An Efficient Arc Consistency Algorithm for a Class of CSP Problems

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's filtering algorithm [20] and culminating in the optimal algorithm AC-4 of Mohr and Henderson [13]. 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 can be instantiated to reduce to AC-3 and AC4. More important, AC-5 can be instantiated to produce an 0(ed) algorithm for two important classes of constraints: functional and monotonic constraints. We et.lso show that AC-5 has an important application in Constraint Logic Programming over Finite Domains [18]. 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).