Variable Elimination in Binary CSPs (Extended Abstract)
Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence
Journal track. Pages 5035-5039. https://doi.org/10.24963/ijcai.2020/702
We investigate rules which allow variable elimination in binary CSP (constraint satisfaction problem) instances while conserving satisfiability. We propose new rules and compare them, both theoretically and experimentally. We give optimised algorithms to apply these rules and show that each defines a novel tractable class. Using our variable-elimination rules in preprocessing allowed us to solve more benchmark problems than without.
Constraints and SAT: Constraint Satisfaction