Fundamental properties of neighbourhood substitution in constraint satisfaction problems

In combinatorial problems it is often worthwhile simplifying the problem, using operations such as consistency, before embarking on an exhaustive search for solutions. Neighbourhood substitution is such a simplification operation. Whenever a value x for a variable is such that it can be replaced in all constraints by another value y, then x is eliminated. This paper shows that neighbourhood substitutions are important whether the aim is to find one or all solutions. It is proved that the result of a convergent sequence of neighbourhood substitutions is invariant module isomorphism. An efficient algorithm is given to find such a sequence. It is also shown that to combine consistency (of any order) and neighbourhood substitution, we only need to establish consistency once.