Using Pivot Consistency to Decompose and Solve Functional CSPs
<|reference_start|>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.<|reference_end|>
@article{david1995using,
    title={Using Pivot Consistency to Decompose and Solve Functional CSPs},
    author={P. David},
    journal={Journal of Artificial Intelligence Research, Vol 2, (1995),
  447-474},
    year={1995},
    archivePrefix={arXiv},
    eprint={cs/9505101},
    primaryClass={cs.AI}
}