2026-08-17T23:43:48Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8487 2024-03-06T10:42:17Z ddc:004 open_access

On Singleton Arc Consistency for CSPs Defined by Monotone Patterns Carbonnel, Clément Cohen, David A. Cooper, Martin C. Zivny, Stanislav constraint satisfaction problems forbidden patterns singleton arc consistency 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Clément Carbonnel and David A. Cohen and Martin C. Cooper and Stanislav Zivny 2018 Is Part Of LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2018.19 urn:nbn:de:0030-drops-84876 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.19 eng https://creativecommons.org/licenses/by/3.0/legalcode