Variable Elimination in Binary CSP via Forbidden Patterns. / Cohen, David; Cooper, Martin C; Escamocher, Guillaume; Zivný, Stanislav.

2013. Paper presented at IJCAI, Beijing, China.

Research output: Contribution to conferencePaperpeer-review



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


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


This open access research output is licenced under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

ID: 16831478