OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

The power of arc consistency for CSPs defined by partially-ordered forbidden patterns

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

Official URL: https://doi.org/10.23638/LMCS-13(4:26)2017


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:
Deposited On:30 Apr 2020 09:13

Repository Staff Only: item control page