Weak consistency notions for all the CSPs of bounded width

DOI10.1145/2933575.2934510MaRDI QIDQ4635924zbMATH OpenOpenAlexFDO

Authors Marcin Kozik

Publication date 23 April 2018

Published in Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1605.00565

zbMATH Keywords

constraint satisfaction problemDataloglocal consistency checking algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Abstract: The characterization of all the Constraint Satisfaction Problems of bounded width, proposed by Feder and Vardi [SICOMP'98], was confirmed in [Bulatov'09] and independently in [FOCS'09, JACM'14]. Both proofs are based on the (2,3)-consistency (using Prague consistency in [FOCS'09], directly in [Bulatov'09]) which is costly to verify. We introduce a new consistency notion, Singleton Linear Arc Consistency (SLAC), and show that it solves the same family of problems. SLAC is weaker than Singleton Arc Consistency (SAC) and thus the result answers the question from [JLC'13] by showing that SAC solves all the problems of bounded width. At the same time the problem of verifying weaker consistency (even SAC) offers significant computational advantages over the problem of verifying (2,3)-consistency which improves the algorithms solving the CSPs of bounded width.

Recommendations

• Solving CSPs using weak local consistency
• On singleton arc consistency for CSPs defined by monotone patterns
• On singleton arc consistency for CSPs defined by monotone patterns
• Theoretical analysis of singleton arc consistency and its extensions
• scientific article; zbMATH DE number 1487982

Cited in

(16)

• On singleton arc consistency for CSPs defined by monotone patterns
• Dismantlability, connectedness, and mixing in relational structures
• Computing weak consistency in polynomial time (extended abstract)
• On singleton arc consistency for CSPs defined by monotone patterns
• scientific article; zbMATH DE number 1942453 (Why is no real title available?)
• scientific article; zbMATH DE number 7359806 (Why is no real title available?)
• Absorption in universal algebra and CSP
• The complexity of valued CSPs
• Solving CSPs using weak local consistency
• Dismantlability, Connectedness, and Mixing in Relational Structures
• Robust algorithms with polynomial loss for near-unanimity CSPs
• Strong subalgebras and the constraint satisfaction problem
• The smallest hard trees
• Collapsing the bounded width hierarchy for infinite-domain constraint satisfaction problems: when symmetries are enough
• Datalog-expressibility for monadic and guarded second-order logic
• There are no pure relational width 2 constraint satisfaction problems

This page was built for publication: Weak consistency notions for all the CSPs of bounded width

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4635924)