OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

Characterising the Complexity of Constraint Satisfaction Problems Defined by 2-Constraint Forbidden Patterns

Cooper, Martin C. and Escamocher, Guillaume Characterising the Complexity of Constraint Satisfaction Problems Defined by 2-Constraint Forbidden Patterns. (2015) Discrete Applied Mathematics, 184. 89-113. ISSN 0166-218X

[img]
Preview
(Document in English)

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

Official URL: http://dx.doi.org/10.1016/j.dam.2014.10.035

Abstract

Although the CSP (constraint satisfaction problem) is NP-complete, even in the case when all constraints are binary, certain classes of instances are tractable. We study classes of binary CSP instances defined by excluding subproblems. This approach has recently led to the discovery of novel tractable classes. The complete characterisation of all tractable classes defined by forbidding patterns (where a pattern is simply a compact representation of a set of subproblems) is a challenging problem. We demonstrate a dichotomy in the case of forbidden patterns consisting of either one or two constraints. This has allowed us to discover several new tractable classes including, for example, a novel generalisation of 2SAT. We then extend this dichotomy to existential patterns whic hare only forbidden on specific domain values.

Item Type:Article
Additional Information:Thanks to Elsevier editor. The definitive version is available at http://www.sciencedirect.com The original PDF of the article can be found at Discrete Applied Mathematics website : www.sciencedirect.com/science/journal/0166218X
HAL Id:hal-01283864
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 - INPT (FRANCE)
Other partners > University College Cork (IRELAND)
Université de Toulouse > Université Toulouse III - Paul Sabatier - UPS (FRANCE)
Université de Toulouse > Université Toulouse - Jean Jaurès - UT2J (FRANCE)
Université de Toulouse > Université Toulouse 1 Capitole - UT1 (FRANCE)
Laboratory name:
Statistics:download
Deposited By: IRIT IRIT
Deposited On:29 Feb 2016 14:58

Repository Staff Only: item control page