Dispensable Instantiations in Constraint Satisfaction Problems

ABSTRACT. 'Simplifying' problems, by removing values or combinations of values, has been a primary approach to combinatorial complexity in constraint satisfaction problems. This paper provides a unifying framework for much of this previous work, and in the process presents new opportunities. It extends a framework for CSP properties provided by Bordeaux, Cadoli, and Mancini. New forms of substitutability and subproblem extraction are introduced. An algorithm for one form of substitutability, neighbourhood replaceability (called "removeability" by Bordeaux et al.), is presented along with preliminary experimental results.