It is polynomial to enforce HC on these cases of the Roots **constraint. However, as**
with the AllDifferent **constraint, it is more effective to use a specialised propagation**
algorithm like that in [27].

Theorem 21 GAC on SymAllDiff **is stronger than HC on the decomposition.**
Proof: Consider X1 ∈ {2, 3}, X2 ∈ {1, 3}, X3 ∈ {1, 2}, {} ⊆ S1 ⊆ {2, 3}, **{} ⊆** S2 ⊆
{1, 3}, and {} ⊆ S3 ⊆ {1, 2}**. Then the decomposition is HC. However, enforcing GAC**
on SymAllDiff([X1, X2, X3**]) will detect unsatisfiability.** ✷
To our knowledge, this constraint has not been integrated into any **constraint solver.**
Thus, this decomposition provides a means of propagation for the SymAllDiff **constraint.**

## 6.3.4 Uses

In Section 6.1.4, we decomposed the constraint Uses with Range **constraints. Another**
way to propagate a Uses constraint is to decompose it using both Range and **Roots**
constraints:
Uses([X1, .., Xn], [Y1, .., Ym**]) iff**
Range([X1, .., Xn], {1, .., n}, T ) ∧
Roots([Y1, .., Ym], {1, .., m}, T )
Enforcing HC on this decomposition is polynomial. Again, such a decomposition hinders propagation as achieving GAC on a Uses **constraint is NP-Hard. Interestingly,**
the decomposition of Uses using Range **constraints presented in Section 6.1.4 and the**
decomposition presented here are equivalent.

Theorem 22 HC on the decomposition of Uses using only Range constraints is equivalent to HC on the decomposition using Range and Roots **constraints.**
Proof: We just need to show that HC on Roots([Y1, .., Ym], {1, .., m}, T **) is equivalent**
to HC on Range([Y1, .., Ym], {1, .., m}, T ′) ∧ T
′ ⊆ T . Since, the Range and the **Roots**
constraints are over the same set of variables ([Y1, .., Ym**]) and the same set of indices**
({1, .., m}**) is fixed for both, then it follows that set variable** T
′ maintained by **Range** is a subset of T maintained by **Roots**. ✷

## 6.4 Open Constraints

Open global constraints have recently been introduced. They are **a new kind of global**
constraints for which the set of variables involved is not fixed. Range and **Roots**
constraints are particularly useful to specify many such open global constraints.

The Gcc constraint has been extended to OpenGcc, a Gcc **constraint for which**
the set of variables involved is not known in advance [34]. Given variables X1, .., Xn and a set variable S, ∅ ⊆ S ⊆ {1..n}, OpenGcc([X1, .., Xn], S, [d1, .., dm], [O1, .., Om**]) holds**