# Decomposition Of The Nvalue Constraint

Christian Bessiere1, George Katsirelos2, Nina Narodytska3, Claude-Guy Quimper4, and Toby Walsh3 1 LIRMM, CNRS, Montpellier, email: bessiere@lirmm.fr 2 CRIL-CNRS, Lens, email: gkatsi@gmail.com 3 NICTA and University of NSW, Sydney, Australia, email:
{nina.narodytska,toby.walsh}@nicta.com.au 4 Universit´e Laval, email: cquimper@gmail.com Abstract. We study decompositions of the global NVALUE constraint. Our main contribution is theoretical: we show that there are propagators for global constraints like NVALUE which decomposition can simulate with the same time complexity but with a much greater space complexity. This suggests that the benefit of a global propagator may often not be in saving time but in saving space. Our other theoretical contribution is to show for the first time that range consistency can be enforced on NVALUE with the same worst-case time complexity as bound consistency. Finally, the decompositions we study are readily encoded as linear inequalities. We are therefore able to use them in integer linear programs.

## 1 Introduction

Global constraints are one of the distinguishing features of constraint programming. They capture common modelling patterns and have associated efficient propagators for pruning the search space. For example, ALL-DIFFERENT is one of the best known global constraints that has proven useful in the modelling and solving of many real world problems. A number of efficient algorithms have been proposed to propagate the ALL-DIFFERENT constraint (e.g. [1–3]). Whilst there is little debate that ALL-DIFFERENT is a global constraint, the formal definition of a global constraint is more difficult to pin down. One property often associated with global constraints is that they cannot be decomposed into simpler constraints without impacting either the pruning or the efficiency of propagation [4]. Recently progress has been made on the theoretical problem of understanding what is and isn't a global constraint. In particular, whilst a bound consistency propagator for the ALL-DIFFERENT constraint can be effectively simulated with a simple decomposition [5], circuit complexity lower bounds have been used to prove that a domain consistency propagator for ALL-DIFFERENT cannot be polynomially simulated by a simple decomposition [6].

In this paper, we turn to a strict generalization of the ALL-DIFFERENT constraint.

NVALUE counts the number of values used by a set of variables; the ALL-DIFFERENT
constraint ensures that this count equals the cardinality of the set. From a theoretical perspective, the NVALUE constraint is significantly more difficult to propagate than the ALL-DIFFERENT constraint since enforcing domain consistency is known to be NPhard [7]. Moreover, as NVALUE is a generalization of ALL-DIFFERENT, there exists no arXiv:1007.0603v1 [cs.AI] 5 Jul 2010