2015/02/12 by David A. Cohen, Martin Cooper, Martin C. Cooper +3
Computer Science · Mathematics · #Advanced Database Systems and Queries #Artificial intelligence #Combinatorics #Computer science #Constraint Satisfaction and Optimization #Constraint satisfaction problem #Data Management and Algorithms #Discrete mathematics #Mathematics #Satisfiability #Statistics #Value (mathematics) #Variable (mathematics) #Variable elimination #cs.AI #cs.CC #cs.DM
paper · pdf · doi:10.1016/j.jcss.2015.02.001
published as Journal of Computer and System Sciences 81(7) 1127-1143 (2015) · A full version of an IJCAI'13 paper to appear in Journal of Computer and System Sciences (JCSS)
arxiv created 2015/02/12 · openalex publication_date 2015/03/06 · arxiv updated 2015/06/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
Variable or value elimination in a constraint satisfaction problem (CSP) can be used in preprocessing or during search to reduce search space size. A variable elimination rule (value elimination rule) allows the polynomial-time identification of certain variables (domain elements) whose elimination, without the introduction of extra compensatory constraints, does not affect the satisfiability of an instance. We show that there are essentially just four variable elimination rules and three value elimination rules defined by forbidding generic sub-instances, known as irreducible existential patterns, in arc-consistent CSP instances. One of the variable elimination rules is the already-known Broken Triangle Property, whereas the other three are novel. The three value elimination rules can all be seen as strict generalisations of neighbourhood substitution.