
## 5.5 Implementation Details

This decomposition of the Roots **constraint can be implemented in many solvers using**
disjunctions of membership and negated membership constraints: or(member(**i, S**), notmember(Xi, T ))
and or(notmember(**i, S**), member(Xi, T **)). However, this requires a little care. Unfortunately, some existing solvers (like Ilog Solver) may not achieve HC on such disjunctions**
of primitives. For instance, the negated membership constraint notmember(Xi, T **) may**
be activated only if Xiis instantiated with a value of T **(whereas it should be as soon as**
D(Xi) ⊆ lb(T **)). We have to ensure that the solver wakes up when it should to ensure**
we achieve HC. As we explain in the complexity proof, we also have to be **careful that** the solver does not wake up too often or we will lose the optimal O(nd**) time complexity** which can be achieved.

Theorem 7 It is possible to enforce HC (or BC) on the decomposition of Roots([X1, .., Xn]**, S, T** )
in O(nd) time, where d = max(∀i.|D(Xi)|, |ub(T )|).

Proof. The decomposition of Roots is composed of 2n **constraints. To obtain an overall**
complexity in O(nd**), the total amount of work spent propagating each of these constraints** must be in O(d**) time.**
First, it is necessary that each of the 2n **constraints of the decomposition is not called**
for propagation more than d times. Since S can be modified up to n times (n **can be** larger than d**) it is important that not all constraints are called for propagation at each** change in lb(S) or ub(S**). By implementing 'propagating events' as described in [20, 30],** we can ensure that when a value i is added to lb(S) or removed from ub(S**), constraints**
j ∈ S → Xj ∈ T and Xj ∈ T → j ∈ S, j 6= i**, are not called for propagation.**
Second, we show that enforcing HC on constraint i ∈ S → Xi ∈ T is in O(d**) time.**
Testing the precondition (does i belong to lb(S**)?) is constant time. If true, removing**
from D(Xi) all values not in ub(T ) is in O(d) time and updating lb(T ) (if |D(Xi)| **= 1) is**
constant time. Testing that the postcondition is false (is D(Xi) disjoint from ub(T **)?) is**
in O(d) time. If false, updating ub(S) is constant time. Thus HC on i ∈ S → Xi ∈ T **is in** O(d) time. Enforcing HC on Xi ∈ T → i ∈ S is in O(d**) time as well because testing the** precondition (D(Xi) ⊆ lb(T )?) is in O(d) time, updating lb(S**) is constant time, testing** that the postcondition is false (i /∈ ub(S**)?) is constant time, and removing from** D(Xi)
all values in lb(T ) is in O(d) time and updating ub(T ) (if |D(Xi)| **= 1) is constant time.**
When T is modified, all constraints are potentially concerned. Since T **can be modified**
up to d times, we can have d calls of the propagation in O(d**) time for each of the 2**n constraints. It is thus important that the propagation of the 2n constraints is **incremental**
to avoid an O(nd2) overall complexity. An algorithm for i ∈ S → Xi ∈ T **is incremental**
if the complexity of calling the propagation of the constraint i ∈ S → Xi ∈ T **up to** d times (once for each change in T or D(Xi**)) is the same as propagating the constraint**
once. This can be achieved by an AC2001-like algorithm that stores the last value found in D(Xi) ∩ ub(T **), which is a witness that the postcondition can be true. (Similarly, the** last value found in D(Xi) \ lb(T **) is a witness that the precondition of the constraint** Xi ∈ T → i ∈ S can be false.) Finally, each time lb(T ) (resp. ub(T **)) is modified,**
D(Xi) must be updated for each i outside ub(S) (resp. inside lb(S**)). If the propagation**
mechanism of the solver provides the values that have been added to lb(T **) or removed**
from ub(T ) to the propagator of the 2n **constraints (as described in [33]), updating a**