variables inside the interval [**b, c**] is greater than or equal to Pn i=1 min(Aibc). The total number of variables XI inside the interval [**b, c**] equals to p P
′ + min(Eb,c). Therefore, i∈X\XI min(Aibc) ≤Pn i=1 min(Aibc) − p
′ − min(Eb,c). On the other hand, the number of values that are not taken by the variables XI in the interval [**b, c**] is c −
b + 1 − p
′. Therefore, we obtain the inequality c − b + 1 − p
′ <Pn i=1 min(Aibc) −
p
′ − min(Eb,c) or min(Ebc) <Pn i=1 min(Aibc) − (c − b **+ 1)**. By construction of I,Pn i=1 min(Aibc) − (c − b + 1) **< min**(Ebc), otherwise the intervals in I that are subsets of [**b, c**] are not maximal. This leads to a contradiction, so we can construct a matching M(E) of size n − min(E1d).

Now suppose that M(E) is not a maximum matching. This means that min(E1d)
is overestimated by propagation on (16) and (19). Since M(E) is not a maximum matching, there exists an augmenting path of M(E), that produces M′, such that |M′| = |M(E)| + 1. This new matching covers all the values that M(E) covers and one additional value q. We show that q cannot belong to the interval [1, d].

The value q cannot be in any interval in I, because all values in [bi, ci] ∈ I are used by variables whose domain is contained in [bi, ci]. In addition, q cannot be in an interval
[**b, c**] between two consecutive intervals in I, because those intervals do not contribute to the lower bound of E1d. Thus, M′cannot cover more values than M(E) and they must have the same size, a contradiction.

We show that when N is BC and dom(N) 6= {**card**↑(X)}, all X variables are BC.

Take any assignment S ∈ ΠXi∈X**range**(Xi) such that card(S) = **card**↑(X). Let S[Xi ← b] be the assignment S where the value of Xiin S has been replaced by b, one of the bounds of Xi. We know that card(S[Xi ← b]) ∈ [card(S) − 1, card(S**) + 1] =**
[card↑(X) − 1, card↑(X**) + 1]** because only one variable has been flipped. Hence, any assignment (**S, p**) with p ≤ **card**↑(X) − 1 is a bound support. dom(N) necessarily contains such a value p by assumption.

We now show that if N = **card**↑(X), enforcing BC on the constraints (16)–(19)
makes the variables X BC with respect to the ATLEASTNVALUE constraint. We first observe that in a bound support, variables X must take the maximum number of different values because N = **card**↑(X). Hence, in a bound support, variables X that are not included in a saturated interval will take values outside any saturated interval they overlap and they all take different values. We recall that min(E1d) = n − |M| =
n − **card**↑(X). Hence, by constraint (19), E1d = n − N. We recall the the size of set XI equals p + E1d. Constraints (18) imply that E1d equals the sum of variables E1,b1−1 + Eb1,c1 + Ec1+1,b2−1 **. . .** + Ebk,ck + Eck+1,d and Pk i=1 min(Ebi,ci) =
|XI | − p = min(E1d) = max(E1d). Hence, by constraints (18), the upper bounds of all variables Ebi,ci that correspond to the saturated intervals are forced to min(Ebi,ci).

Thus, by constraints (16) and (17), all variables in X \ XI have their bounds pruned if they belong to Dk I
. By constraints (18) again, the upper bounds of all variables Elu that correspond to the unsaturated intervals are forced to take value 0, and all variables El
′u′ with [l
′, u′] ⊆ [**l, u**] are forced to 0 as well. Thus, by constraints (16) and (17), all variables in X \ XI have their bounds pruned if they belong to a Hall interval of other variables in X \ XI . This is what BC on the ALL-DIFFERENT constraint does [5].

There are O(nd2) constraints (16) that can be woken O(d) times down the branch of the search tree in O(1), so a total of O(nd3) down the branch. There are O(d 2)