Abstract Bessière et al. (AAAI’08) showed that several intractable global constraints can be ef?ciently propagated when certain natural problem parameters are small. In particular, the complete propagation of a global constraint is ?xed-parameter tractable in k – the number of holes in domains – whenever bound consistency can be enforced in polynomial time; this applies to the global constraints AT M OST-NVALUE and E X TENDED G LOBAL C ARDINALITY (EGC). In this paper we extend this line of research and introduce the concept of reduction to a problem kernel, a key concept of parameterized complexity, to the ?eld of global constraints. In particular, we show that the consistency problem for AT M OST-NVALUE constraints admits a linear time reduction to an equivalent instance on O(k 2 ) variables and domain values. This small kernel can be used to speed up the complete propagation of NVALUE constraints. We contrast this result by showing that the consistency problem for EGC constraints does not admit a reduction to a polynomial problem kernel unless the polynomial hierarchy collapses.