OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

On Singleton Arc Consistency for CSPs Defined by Monotone Patterns

Carbonnel, Clément and Cohen, David and Cooper, Martin and Zivny, Stanislav On Singleton Arc Consistency for CSPs Defined by Monotone Patterns. (2018) Algorithmica, 81 (4). 1699-1727. ISSN 0178-4617

[img]
Preview
(Document in English)

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

Official URL: https://doi.org/10.1007/s00453-018-0498-2

Abstract

Singleton arc consistency is an important type of local consistency which has been recently shown to solve all constraint satisfaction problems (CSPs) over constraint languages of bounded width. We aim to characterise all classes of CSPs defined by a forbidden pattern that are solved by singleton arc consistency and closed under removing constraints. We identify five new patterns whose absence ensures solvability by singleton arc consistency, four of which are provably maximal and three of which generalise 2-SAT. Combined with simple counter-examples for other patterns, we make significant progress towards a complete classification.

Item Type:Article
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 > Royal Holloway University of London - RHUL (UNITED KINGDOM)
Other partners > University of Oxford (UNITED KINGDOM)
Laboratory name:
Statistics:download
Deposited On:12 Mar 2020 13:32

Repository Staff Only: item control page