Table 1. Backtracks and rumtime (in seconds) to solve the dominating set problem for the Queen's graph. Best results for any statistic are bold fonted.

| n N        | Occs            | Occsgcc          | P yramidBC      | P yramidRC    |              |      |     |      |
|------------|-----------------|------------------|-----------------|---------------|--------------|------|-----|------|
| backtracks | time backtracks | time backtracks  | time backtracks | time          |              |      |     |      |
| 5 3        | 34              | 0.01             | 34              | 0.06          | 7            | 0.00 | 7   | 0.00 |
| 6 3        | 540             | 0.16             | 540             | 2.56          | 118          | 0.03 | 118 | 0.03 |
| 7 4        | 195,212         | 84.50            | 195,212 1681,21 | 83,731 15.49  | 83,731 21.21 |      |     |      |
| 8 5        | 390,717 255.64  | 390,717 8,568.35 | 256,582 58.42   | 256,582 89.30 |              |      |     |      |

## 7.2 Random Binary Csp Problems

We also reproduced the set of experiments on random binary CSP problems from [5].

These problems can be described by four parameters. The number of variables n, the domain size d, the number of binary constraints m and the number of forbidden tuples in each binary constraint. The first three classes are hard problems at the phase transition in satisfiability. The last two classes are under-constrained problems. We add a single ATMOSTNVALUE constraint over all variables to bound the number of values N that can be used in a solution.

As in [5], we generated 500 instances for each of the following 5 classes:
- class A : n = 100, d = 10, m = 250, t = 52, N = 8 - class B : n = 50, d = 15, m = 120, t = 116, N = 6 - class C : n = 40, d = 20, m = 80, t = 240, N = 6 - class D : n = 200, d = 15, m = 600, t = 85, N = 8
- class E : n = 60, d = 30, m = 150, t = 350, N = 6 All instances are solved using the minimum domain variable ordering heuristic, a lexicographical value ordering and a timeout of 600 seconds. We use the same decompositions of the ATMOSTNVALUE constraint as in the experiments with the dominating set of the Queen's graph. Results are given in Table 2. On classes **A, B, C** (hard problems), our decomposition is faster than the other two decompositions and solves more instances whatever we use BC or RC. On classes **D, E** (under-constrained problems),
enforcing BC on our decomposition does not prune the search space enough. This leads to a high number of backtracks and a significant slow down. Our decomposition with RC is again better than the other decompositions.

These experiments demonstrate that this new decomposition is efficient to use in practice. Of course, if the toolkit contains a specialized BC propagator for the NVALUE
constraint, we will probably do best to use this. However, when the toolkit lacks such a propagator (as is often the case), it is reasonable to try out our decomposition.

## 8 Other Related Work

Decompositions have been given for a number of other global constraints. For example, Beldiceanu *et al.* identify conditions under which global constraints specified as automata can be decomposed into signature and transition constraints without hindering