Abstract
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.
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 language | English |
|---|---|
| Publication status | Published - 2013 |
| Event | IJCAI - Beijing, China Duration: 3 Aug 2013 → 9 Aug 2013 |
Conference
| Conference | IJCAI |
|---|---|
| Country/Territory | China |
| City | Beijing |
| Period | 3/08/13 → 9/08/13 |