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 C. and Zivny, Stanislav On singleton arc consistency for CSPs defined by monotone patterns. (2018) In: 35th International Symposium on Theoretical Aspects of Computer Science (STACS 2018), 28 February 2018 - 3 March 2018 (Caen, France).

(Document in English)

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

Official URL: https://doi.org/10.4230/LIPIcs.STACS.2018.19


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:Conference or Workshop Item (Paper)
Additional Information:Thanks to Dagstuhl Research Online Publication Server (DROPS) Distribution of this paper is permitted under the terms of the Creative Commons license CC-by-nc-nd 4.0. This papers appears in Proceedings of STACS 2018 ISBN 978-3-95977-062-0 The definitive version is available at: https://drops.dagstuhl.de/opus/volltexte/2018/8487/pdf/LIPIcs-STACS-2018-19.pdf
Audience (conference):International conference proceedings
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:
Deposited On:30 Sep 2020 07:51

Repository Staff Only: item control page