FUNDAMENTAL PROPERTIES OF NEIGHBORHOOD SUBSTITUTION IN CONSTRAINT SATISFACTION PROBLEMS

In combinatorial problems it is often worthwhile simplifying the probl em, using operations such as consistency, before embarking on an exhau stive search for solutions. Neighbourhood substitution is such a simpl ification 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 elim inated. This paper shows that neighbourhood substitutions are importan t whether the aim is to find one or all solutions. It is proved that t he result of a convergent sequence of neighbourhood substitutions is i nvariant module isomorphism. An efficient algorithm is given to find s uch a sequence. It is also shown that to combine consistency (of any o rder) and neighbourhood substitution, we only need to establish consis tency once.