Using Pivot Consistency to Decompose and Solve Functional CSPs
  Many studies have been carried out in order to increase the search efficiency
of constraint satisfaction problems; among them, some make use of structural
properties of the constraint network; others take into account semantic
properties of the constraints, generally assuming that all the constraints
possess the given property. In this paper, we propose a new decomposition
method benefiting from both semantic properties of functional constraints (not
bijective constraints) and structural properties of the network; furthermore,
not all the constraints need to be functional. We show that under some
conditions, the existence of solutions can be guaranteed. We first characterize
a particular subset of the variables, which we name a root set. We then
introduce pivot consistency, a new local consistency which is a weak form of
path consistency and can be achieved in O(n^2d^2) complexity (instead of
O(n^3d^3) for path consistency), and we present associated properties; in
particular, we show that any consistent instantiation of the root set can be
linearly extended to a solution, which leads to the presentation of the
aforementioned new method for solving by decomposing functional CSPs.
