OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

Variable and Value Elimination in Binary Constraint Satisfaction via Forbidden Patterns

Cohen, David A. and Cooper, Martin C. and Escamocher, Guillaume and Zivny, Stanislav Variable and Value Elimination in Binary Constraint Satisfaction via Forbidden Patterns. (2015) Journal of Computer and System Sciences, 81 (7). 1127-1143. ISSN 0022-0000

(Document in English)

PDF (Author's version) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader

Official URL: http://dx.doi.org/10.1016/j.jcss.2015.02.001


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.

Item Type:Article
Additional Information:Thanks to Elsevier editor. The definitive version is available at tp://www.sciencedirect.com The original PDF of the article can be found at Journal of Computer and System Sciences website : http://www.sciencedirect.com/science/journal/00220000
HAL Id:hal-01280349
Audience (journal):International peer-reviewed journal
Uncontrolled Keywords:
Institution:French research institutions > Centre National de la Recherche Scientifique - CNRS (FRANCE)
Université de Toulouse > Institut National Polytechnique de Toulouse - Toulouse INP (FRANCE)
Other partners > University College Cork (IRELAND)
Université de Toulouse > Université Toulouse III - Paul Sabatier - UT3 (FRANCE)
Université de Toulouse > Université Toulouse - Jean Jaurès - UT2J (FRANCE)
Université de Toulouse > Université Toulouse 1 Capitole - UT1 (FRANCE)
Other partners > University of London (UNITED KINGDOM)
Other partners > University of Oxford (UNITED KINGDOM)
Laboratory name:
Deposited On:10 Feb 2016 13:28

Repository Staff Only: item control page