We now prove that this decomposition does not hinder propagation in general.

Theorem 4 *BC on the constraints* (16) to (19) *is equivalent to BC on* ATLEASTNVALUE ([X1, . . . , Xn], N), and takes O(nd3) *time to enforce down the* branch of the search tree.

Proof: First note that changing the domains of the X variables cannot affect the lower bound of N by the ATLEASTNVALUE constraint and, conversely, changing the upper bound of N cannot affect the domains of the X variables.

It is known [12] that **card**↑(X) is equal to the size of a maximum matching M in the value graph of the constraint. Since N ≤ n − E1d, we show that the lower bound of E1d is equal to n− |M|.

5 We first show that we can construct a matching M(E) of size n − min(E1d), then show that it is a maximum matching. The proof uses a partition of the interval [1, d] into a set of maximal saturated intervals I = {[bj, cj ]}, j = 1**, . . . , k**
such that min(Ebj ,cj) = Pn i=1 min(Aibj cj) − (cj − bj **+ 1)** and a set of unsaturated intervals {[bj, cj ]}such that min(Ebj ,cj**) = 0**.

Let I = {[bj, cj ] | j ∈ [1 **. . . k**]} be the ordered set of maximal intervals such that min(Ebj ,cj) = Pn i=1 min(Aibj cj) − (cj − bj **+ 1)**. Note that the intervals in I are disjoint otherwise intervals are not maximal. An interval [bi, ci] is smaller than [bj , cj ] iff ci < bj. We denote the union of the first j intervals D
j I =Sj i=1[bi, ci],
j = [1**, . . . , k**], p = |Dk I
| and the variables whose domain is inside one of intervals I
XI = {Xpi|dom(Xpi) ⊆ Dk I
}.

Our construction of a matching uses two sets of variables, XI and X \ XI . First, we identify the cardinality of these two sets. Namely, we show that the size of the set XI is p + min(E1,d) and the size of the set X \ XI is n − (p + min(E1,d)).

Intervals I are saturated therefore each value from these intervals are taken by a variable in XI . Therefore, XI has size at least p. Moreover, there exist min(E1d)
additional variables that take values from Dk I
, because values from intervals between two consecutive intervals in I do not contribute to the lower bound of the variable E by construction of I. Therefore, the number of variables in Dk I
is at least p + min(E1,d). Note that constraints (18) imply that E1d equals the sum of variables E1,b1−1 + Eb1,c1 + Ec1+1,b2−1 **. . .** + Ebk,ck + Eck+1,d. As intervals in I
are disjoint then Pk i=1 min(Ebi,ci) = |XI | − p. If |XI | > p + min(E1,d) then Pk i=1 min(Ebi,ci) **> min**(E1,d) and the lower bound of the variable E1d will be increased. Hence, |XI | = p + min(E1,d).

Since all these intervals are saturated, we can construct a matching MI of size p using the variables in XI . The size of X \ XI is n − p − min(E1d). We show by contradiction that we can construct a matching MD−Dk I
of size n − p − min(E1d)
using the variables in X \ XI and the values D − Dk I
.

Suppose such a matching does not exist. Then, there exists an interval [**b, c**] such that |(D \ Dk I
) ∩ [b, c]| <Pi∈X\XI min(Aibc), i.e., after consuming the values in I with variables in XI , we are left with fewer values in [**b, c**] than variables whose domain is contained in [**b, c**]. We denote p
′ = |[**b, c**] ∩ Dk I
|, so that p
′is the number of values inside the interval [**b, c**] that are taken by variables in XI . The total number of 5 We assume that E1d is not pruned by other constraints.