
## 5 Propagating The Roots **Constraint**

We now give a thorough theoretical analysis of the Roots **constraint. In Section 5.1,** we provide a proof that enforcing HC on Roots **is NP-hard in general. Section 5.2** presents a decomposition of the Roots **constraint that permits us to propagate the** Roots constraint partially in linear time. Section 5.3 shows that in many cases **this**
decomposition does not destroy the global nature of the Roots **constraint as enforcing** HC on the decomposition achieves HC on the Roots **constraint. Section 5.4 shows** that we can obtain BC on the Roots **constraint by enforcing BC on its decomposition.**
Finally, we provide some implementation details in Section 5.5.

## 5.1 Complete Propagation

Unfortunately, propagating the Roots **constraint completely is intractable in general.**
Whilst we made this claim in [10], a proof has not yet been published. For this reason, we give one here.

Theorem 3 Enforcing HC on the Roots **constraint is NP-hard.**
Proof. We transform 3Sat into the problem of the existence of a solution for **Roots**. Finding a hybrid support is thus NP-hard. Hence enforcing HC on Roots **is NP-hard.**
Let ϕ = {c1, . . . , cm} be a 3CNF on the Boolean variables x1, . . . , xn. We build the constraint Roots([X1, . . . , Xn+m], S, T ) as follows. Each Boolean variable xi**is represented**
by the variable Xi with domain D(Xi) = {i, −i}. Each clause cp = xi ∨ ¬xj ∨ xk is represented by the variable Xn+p with domain D(Xn+p) = {i, −j, k}. We build S and T in such a way that it is impossible for both the index i of a Boolean variable xi and its complement −i to belong to T . We set lb(T ) = ∅ and ub(T ) = Sn i=1{i, −i}**, and**
lb(S) = ub(S) = {n + 1, . . . , n + m}. An interpretation M **on the Boolean variables**
x1, . . . , xn is a model of ϕ iff the tuple τ in which τ[Xi] = i iff M[xi**] = 0 can be extended**
to a solution of Roots. (This extension puts in T value i iff M[xi**] = 1 and assigns** Xn+p with the value corresponding to the literal satisfying cp in M.) ✷
We thus have to look for a lesser level of consistency for Roots **or for particular cases**
on which HC is polynomial. We will show that bound consistency is tractable and that, under conditions often met in practice (e.g. one of the last two arguments of **Roots** is ground), enforcing HC is also.

## 5.2 A Decomposition Of **Roots**

To show that Roots can be propagated tractably, we will give a straightforward decomposition into ternary constraints that can be propagated in linear time. This decomposition does not destroy the global nature of the Roots **constraint since enforcing HC on**
the decomposition will, in many cases, achieve HC on the original Roots **constraint, and** since in all cases, enforcing BC on the decomposition achieves BC on the original **Roots**
constraint. Given Roots([X1, .., Xn], S, T **), we decompose it into the implications:**