  We argue that parameterized complexity is a useful tool with which to study
global constraints. In particular, we show that many global constraints which
are intractable to propagate completely have natural parameters which make them
fixed-parameter tractable and which are easy to compute. This tractability
tends either to be the result of a simple dynamic program or of a decomposition
which has a strong backdoor of bounded size. This strong backdoor is often a
cycle cutset. We also show that parameterized complexity can be used to study
other aspects of constraint programming like symmetry breaking. For instance,
we prove that value symmetry is fixed-parameter tractable to break in the
number of symmetries. Finally, we argue that parameterized complexity can be
used to derive results about the approximability of constraint propagation.

Artificial Intelligence;Computational Complexity