Lifting Structural Tractability to CSP with Global Constraints
  A wide range of problems can be modelled as constraint satisfaction problems
(CSPs), that is, a set of constraints that must be satisfied simultaneously.
Constraints can either be represented extensionally, by explicitly listing
allowed combinations of values, or implicitly, by special-purpose algorithms
provided by a solver. Such implicitly represented constraints, known as global
constraints, are widely used; indeed, they are one of the key reasons for the
success of constraint programming in solving real-world problems.
  In recent years, a variety of restrictions on the structure of CSP instances
that yield tractable classes have been identified. However, many such
restrictions fail to guarantee tractability for CSPs with global constraints.
In this paper, we investigate the properties of extensionally represented
constraints that these restrictions exploit to achieve tractability, and show
that there are large classes of global constraints that also possess these
properties. This allows us to lift these restrictions to the global case, and
identify new tractable classes of CSPs with global constraints.
