Variable Elimination in Binary CSP via Forbidden Patterns

David Cohen, Martin C Cooper, Guillaume Escamocher, Stanislav Zivný

Research output: Contribution to conferencePaperpeer-review

142 Downloads (Pure)


A variable elimination rule allows the polynomial-
time identification of certain variables whose elim-
ination does not affect the satisfiability of an in-
stance. Variable elimination in the constraint sat-
isfaction problem (CSP) can be used in prepro-
cessing or during search to reduce search space
size. We show that there are essentially just four
variable elimination rules defined by forbidding
generic sub-instances, known as irreducible pat-
terns, in arc-consistent CSP instances. One of these
rules is the Broken Triangle Property, whereas the
other three are novel.
Original languageEnglish
Publication statusPublished - 2013
EventIJCAI - Beijing, China
Duration: 3 Aug 20139 Aug 2013



Cite this