Complexity of the Cardpath Constraint

The cardpath constraint enforces a constraint C to be satisfied a given number of times over a sequence of variables. In this note, we give a polynomial propagation algorithm for a special case of this constraint, which in fact is the only case which was not known to be intractable. The cardinality path constraint [BC01], cardpath(N, [X1, . . . , Xm], C), where C is a constraint of arity k < m and N is an integer variable, ensures that N = ∑m−k+1 i=1 C(Xi, . . . , Xi+k−1). (C() returns 1 when satisfied, 0 otherwise.) In other words, we slide C down the sequence X1, . . . , Xm and ensure it holds N times. In [BHHW04a] and [BHHW04b], we proved that enforcing arc consistency on the constraint cardpath(N, [X1, . . . , Xm], C) is NP-hard if C has unbounded arity (even if arc consistency is polynomial on it) or if we allow repetition of variables in the sequence X1, . . . , Xm. The only remaining open question was therefore about the complexity of cardpath when C has bounded arity and we don’t allow repetitions in X1, . . . , Xm. We show that it is in fact polynomial to achieve arc consistency on such a constraint. We present an algorithm for C being binary, which is simpler to present. But the technique can be extended to any arity as long as it remains bounded. The idea of the algorithm is the following. It first makes a double traversal of the sequence [X1, . . . , Xm], one from X1 to Xm (lines 1 to 7) and the other from Xm downto X1 (lines 8 to 14). This step computes two sets of integers, w(Xi, v) and dw(Xi, v) for each value (Xi, v). The set w(Xi, v) contains all possible number of times C is satisfied by a tuple on [X1, . . . , Xi] belonging to D(X1) × · · · × D(Xi), while dw(Xi, v) contains all possible number of times C is satisfied by a tuple on [Xi, . . . , Xm] in D(Xi)× · · · × D(Xm). The second step (lines 15 to 18) makes the join of those two sets of integers, putting in the set T (Xi, v) all possible number of times C is satisfied by a complete tuple in D(X1)× · · ·×D(Xm). All values such that T (Xi, v) does not intersect D(N) are removed since there does not exist any tuple in D(X1) × · · · × D(Xm), using v for Xi that satisfies C a number of times allowed by N .