Strengthening neighbourhood substitution
This work addresses domain reduction for constraint satisfaction problems, which is incremental as it builds on existing neighbourhood substitution methods.
The authors tackled the problem of domain reduction in binary constraint satisfaction by strengthening the concept of neighbourhood substitution in two ways without increasing time complexity, and they proved that finding an optimal sequence of these new operations is NP-hard.
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.