iff |{i ∈ S | Xi = dj}| = Oj for all j. OpenGcc can be decomposed into a set of **Roots**
constraints in almost the same way as Gcc **was decomposed in Section 6.2.1:**

OpenGcc([X1, .., Xn], S, [d1, .., dm], [O1, .., Om**]) iff**
$S=\bigcup\limits_{i\in1..m}S_{i}\ \wedge$  $\forall i\.\ \mbox{Roots}([X_{1},..,X_{n}],S_{i},\{d_{i}\})\ \wedge\ |S_{i}|=O_{i}$  $\forall i\.\ \mbox{Rocons}([X_{1},..,X_{n}],S_{i},\{d_{i}\})\ \wedge\ |S_{i}|=O_{i}$
Propagators for such an open constraint have not yet been included in constraint solvers. In [34], a propagator is proposed for the case where Oi**'s are ground intervals.**
In the decomposition above, the Oi's can either be variables or ground intervals. However, even when Oi**'s are ground intervals, both the decomposition and the propagator**
presented in [34] hinder propagation and are incomparable to each **other.**
Theorem 23 Even if Oi's are ground intervals, (1) HC on the OpenGcc **constraint is**
stronger than HC on the decomposition using Roots **constraints, (2) the propagator in**
[34] and HC on the decomposition using Roots **constraints are incomparable.**
Proof: (1) Consider X1, X2 ∈ {1, 2}, X3 ∈ {1, 2, 3}, di = i, S = {1, 2, 3} and O1, O2, O3 = [0, 1]. The decomposition is HC (with {} ⊆ S1, S2 ⊆ {1, 2, 3} and **{} ⊆**
S3 ⊆ {3}). However, enforcing HC on the OpenGcc **constraint will prune 1 and 2 from**
X3.

(2) Consider the example in case (1). The propagator in [34] will prune 1 and 2 from X3 whereas the decomposition is HC. Consider X1 ∈ {1, 2}, X2 ∈ {2, 3}, X3 ∈ {3, 4}, di = i, {} ⊆ S ⊆ {1, 2, 3} and O1 = [1, 1], O2 = [0, 1], O3 = [0, 0], O4 = [0, **0]. The**
propagator in [34] will prune the only value in the Xi **variables which is not HC, that** is, value 2 for X1. It will not prune the bounds on S**. However, enforcing HC on the**
decomposition using Roots constraints will set S1 = {1}**, then will prune value 2 for**
X1, will shrink S2 to {} ⊆ S2 ⊆ {2}, will set S3 = S4 = {} **and will finally shrink** S to
{1} ⊆ S ⊆ {1, 2}. ✷
As observed in [34], the definition of OpenGcc **subsumes the definition for the open**
version of the AllDifferent constraint. Given variables X1, .., Xn **and a set variable**
S, ∅ ⊆ S ⊆ {1..n}, OpenAllDifferent([X1, .., Xn], S) holds iff Xi 6= Xj, ∀**i, j** ∈ S.

Interestingly, this constraint can be decomposed using Range **in almost the same way** as AllDifferent **was decomposed in Section 6.1.1.**
OpenAllDifferent([X1, .., Xn], S**) iff**
Range([X1, .., Xn], S, T ) ∧ |S| = |T | Not surprisingly, this decomposition hinders propagation (see the example used in Theorem 8 to show that the decomposition of AllDifferent using Range **hinders**
propagation). Nevertheless, as in the case of OpenGcc, we do not know of any polynomial algorithm for achieving HC on **OpenAllDifferent**.