
## 2 Background

We assume values are taken from the set 1 to d. We write dom(Xi) for the domain of possible values for Xi, min(Xi) for the smallest value in dom(Xi), max(Xi) for the greatest, and **range**(Xi) for the interval [min(Xi)**, max**(Xi)]. A *global constraint* is one in which the number of variables n is a parameter. For instance, the global NVALUE([X1, . . . , Xn], N) constraint ensures that N = |{Xi| 1 ≤ i ≤ n}| [1].

Constraint solvers typically use backtracking search to explore the space of partial assignments. After each assignment, propagation algorithms prune the search space by enforcing local consistency properties like domain, range or bound consistency. A constraint is domain consistent (DC) iff when a variable is assigned any of the values in its domain, there exist compatible values in the domains of all the other variables of the constraint. Such an assignment is called a *support*. A constraint is *disentailed* iff there is no possible support. A constraint is range consistent (RC) iff, when a variable is assigned any of the values in its domain, there exist compatible values between the minimum and maximum domain value for all the other variables of the constraint. Such an assignment is called a *bound support*. A constraint is *bound consistent* (BC) iff the minimum and maximum value of every variable of the constraint belong to a bound support. We will compare local consistency properties applied to sets of constraints, c1 and c2 which are logically equivalent. As in [7], a local consistency property Φ on c1 is as strong as Ψ on c2 iff, given any domains, if Φ holds on c1 then Ψ holds on c2; Φ on c1 is stronger than Ψ on c2 iff Φ on c1 is as strong as Ψ on c2 but not vice versa; Φ on c1 is equivalent to Ψ on c2 iff Φ on c1 is as strong as Ψ on c2 and vice versa. Finally, as constraint solvers usually enforce local consistency after each assignment down a branch in the search tree, we will compute the total amortised cost of enforcing a local consistency down an entire branch of the search tree. This captures the incremental cost of propagation.

## 3 Nvalue Constraint

Pachet and Roy proposed the NVALUE constraint (called by them the "cardinality on attribute values" constraint) to model a combinatorial problem in selecting musical playlists [1]. It can also be used to model the number of frequencies used in a frequency allocation problem or the number of rooms needed to timetable a set of exams. It generalizes several other global constraints including ALL-DIFFERENT (which ensures a set of variables take all different values) and NOT-ALL-EQUAL (which ensures a set of variables do not all take the same value). Enforcing domain consistency on the NVALUE
constraint is NP-hard (Theorem 3 in [2]) even when N is fixed (Theorem 2 in [4]). In fact, computing the lower bound on N is NP-hard (Theorem 3 in [8]). In addition, enforcing domain consistency on the NVALUE constraint is not fixed parameter tractable since it is in the W[2]-complete complexity class along with problems like minimum hitting set (Theorem 2 in [9]). However, a number of polynomial propagation algorithms have been proposed that achieve bound consistency and some closely related levels of local consistency [3–5].