Structural Tractability of Propagated Constraints

Modern constraint solvers do trot require constraints to l), represented using ally particular data structure. Instead, constraints rue given as black boxes known as propagators. Propagators are given a. list of current domains for variables and are :allowed to prune values not. consistent with these current domains.

Using propagation as the only primitive operation on constraints imposes restrictions on the operations that can be performed in polynomial time. In the extensional representation of constraints (so-called positive table constraints) join and project are primitive polynomial-time operations. This is not true for propagated constraints.

The question we pose ill this paper is: If propagation is the only primitive operation, what are: the: structurally tractable classes of constraint programs (whose instances can he solved in polynomial time)?

We consider a hierarchy of propagators: arbitrary propagators, whose only ability is consistency checking; partial assignment membership propagators, which allow us to check partial assignments; and generalised arc consistency propagators, the strongest, form of propagator.

In the first two cases, we answer the posed question by establishing dichotomies. In the case of generalised are consistency propagators, we achieve a useful dichotomy in the restricted case: of acyclic structures.