  Domain reduction is an essential tool for solving the constraint satisfaction
problem (CSP). In the binary CSP, neighbourhood substitution consists in
eliminating a value if there exists another value which can be substituted for
it in each constraint. We show that the notion of neighbourhood substitution
can be strengthened in two distinct ways without increasing time complexity. We
also show the theoretical result that, unlike neighbourhood substitution,
finding an optimal sequence of these new operations is NP-hard.
