Algorithm 1: Hybrid consistency on **Range**
procedure Propag-Range([X1, . . . , Xn]**, S, T**);
1 Introduce the set of integer variables Y = {Yi | i ∈ ub(S)},
with D(Yi) = D(Xi) ∪ {**dummy**};
2 Achieve hybrid consistency on the constraint Occurs(**Y, T**);
3 Achieve hybrid consistency on the constraints i ∈ S ↔ Yi ∈ T, for all Yi ∈ Y ; 4 Achieve GAC on the constraints (Yi = **dummy**) ∨ (Yi = Xi), for all Yi ∈ Y ;
Incrementality. In constraint solvers, constraints are usually maintained **in a locally**
consistent state after each modification (restriction) of the domains of the variables. It is thus interesting to consider the total complexity of maintaining HC on Occurs **after**
an arbitrary number of restrictions on the domains (values removed from D(Xi**) and**
ub(T ), or added to lb(T **)) as we descend a branch of a backtracking search tree. Whereas**
some constraints are completely incremental (i.e., the total complexity after any number of restrictions is the same as the complexity of one propagation), this is not the case for constraints based on flow techniques like AllDifferent or Gcc **[25, 26]. They**
potentially require the computation of a new maximum flow after each **modification.**
Restoring a maximum flow from one that lost p edges is in O(p · e**). If values are removed**
one by one (nd **possible times), and if each removal affects the current maximum flow,**
the overall complexity over a sequence of restrictions on Xi's, S, T **, is in** O(n 2d 2).

## 4.2 Hybrid Consistency On **Range**

Enforcing HC on Range([X1, . . . , Xn], S, T ) can be done by decomposing it as an **Occurs**
constraint on new variables Yi and some channelling constraints ([16]) linking T **and the**
Yi's to S and the Xi's. Interestingly, we do not need to maintain HC on the decomposition but just need to propagate the constraints in **one pass**.

The algorithm Propag-Range, enforcing HC on the Range **constraint, is presented in**
Algorithm 1. In line 1, a special encoding is built, where a Yi**is introduced for each** Xi with index in ub(S). The domain of a Yiis the same as that of Xi **plus a dummy value.**
The dummy value works as a flag. If Occurs prunes it from D(Yi**) this means that** Yiis necessary in Occurs to cover lb(T ). Then, Xiis also necessary to cover lb(T ) in **Range**. In line 1, HC on Occurs removes a value from a Yi **each time it contains other values**
that are necessary to cover lb(T **) in every solution tuple. HC also removes values from**
ub(T ) that cannot be covered by any Yi**in a solution. Line 1 updates the bounds of** S and the domain of Yi's. Finally, in line 1, the channelling constraints between Yi and Xi propagate removals on Xi for each i which belongs to S **in all solutions.**
Theorem 2 **The algorithm Propag-Range is a correct algorithm for enforcing HC on**
Range, that runs in O(nd + n · |lb(T )| 3/2) time, where d **is the maximal size of** Xi domains.

Proof. Soundness. A value v is removed from D(Xi**) in line 1 if it is removed from** Yi together with dummy in lines 1 or 1. If a value v is removed from Yi**in line 1, this means** that any tuple on variables in Y covering lb(T ) requires that Yi **takes a value from** D(Yi)