
## 6.3.2 Common

A generalization of the Among and AllDifferent **constraints introduced in [2] is the**
Common constraint. Common(N, M, [X1, .., Xn], [Y1, .., Ym]) ensures N = |{i | ∃**j, X**i =
Yj}| and M = |{j | ∃i, Xi = Yj}|. That is, N variables in Xi **take values in common with**
Yj and M variables in Yj takes values in common with Xi**. We prove that we cannot**
expect to enforce GAC on such a constraint as it is NP-hard to do so **in general.**
Theorem 19 Enforcing GAC on Common **is NP-hard.**
Proof: We again use a transformation from 3-SAT. Consider a formula ϕ with n **Boolean**
variables and m clauses. For each Boolean variable i, we introduce a variable Xi ∈ {i, −i}.

For each clause cj = x ∨ ¬y ∨ z, we introduce Yj ∈ {x, −y, z}. We let N ∈ {0, .., n} and M = m. ϕ has a model iff the Common constraint has a solution in which the Xi **take**
the literals true in this model. ✷
One way to propagate a Common constraint is to decompose it into Range and Roots **constraints:**
Common(N, M, [X1, .., Xn], [Y1, .., Ym**]) iff**
Range([Y1, .., Ym], {1, .., m}, T ) ∧ Roots([X1, .., Xn], S, T ) ∧ |S| = N ∧ Range([X1, .., Xn], {1, .., n}, V ) ∧
Roots([Y1, .., Ym], U, V ) ∧ |U| = M
Enforcing HC on this decomposition is polynomial. Decomposition thus offers a simple method to propagate a Common **constraint. Not surprisingly, the decomposition**
hinders propagation.

Theorem 20 GAC on Common **is stronger than HC on the decomposition.**
Proof: Consider N = M = 0, X1, Y1 ∈ {1, 2}, X2, Y2 ∈ {1, 3}, Y3 ∈ {2, 3}**. Hybrid**
consistency on the decomposition enforces {} ⊆ T, V ⊆ {1, 2, 3}, and S = U = {} **but no**
pruning on the Xi and Yj . However, enforcing GAC on Common(N, M, [X1, X2], [Y1, Y2, Y3])
prunes 2 from X1, 3 from X2 and 1 from both Y1 and Y2. ✷

## 6.3.3 Symmetric All Different

In certain domains, we may need to find symmetric solutions. For example, in sports scheduling problems, if one team is assigned to play another then the **second team should**
also be assigned to play the first. SymAllDiff([X1, .., Xn]) ensures Xi = j iff Xj = i
[27]. It can be decomposed into a set of Range and Roots **constraints:**
SymAllDiff([X1, .., Xn**]) iff**
Range([X1, .., Xn], {1, .., n}, {1**, .., n**}) ∧
∀i . Roots([X1, .., Xn], Si, {i}) ∧ Xi ∈ Si ∧ |Si| = 1