Cooper, Martin C. and Zivny, Stanislav
The power of arc consistency for CSPs defined by partially-ordered forbidden patterns.
(2017)
Logical Methods in Computer Science, 13 (4:26). 1-32. ISSN 1860-5974
|
(Document in English)
PDF (Publisher's version) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader 616kB |
Official URL: https://doi.org/10.23638/LMCS-13(4:26)2017
Abstract
Characterising tractable fragments of the constraint satisfaction problem (CSP) is an important challenge in theoretical computer science and arti ficial intelligence. Forbidding patterns (generic sub-instances) provides a means of defi ning CSP fragments which are neither exclusively language-based nor exclusively structure-based. It is known that the class of binary CSP instances in which the broken-triangle pattern (BTP) does not occur, a class which includes all tree-structured instances, are decided by arc consistency (AC), a ubiquitous reduction operation in constraint solvers. We provide a characterisation of simple partially-ordered forbidden patterns which have this AC-solvability property. It turns out that BTP is just one of fi ve such AC-solvable patterns. The four other patterns allow us to exhibit new tractable classes.
Item Type: | Article |
---|---|
HAL Id: | hal-02640799 |
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) 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 Oxford (UNITED KINGDOM) |
Laboratory name: | |
Statistics: | download |
Deposited On: | 30 Apr 2020 09:13 |
Repository Staff Only: item control page