Weaker consistency notions for all the CSPs of bounded width

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.

Cited by in corpus (9)

• CLAP: A New Algorithm for Promise CSPs
• Strong subalgebras and the Constraint Satisfaction Problem
• Examples, counterexamples, and structure in bounded width algebras
• Exploring Directional Path-Consistency for Solving Constraint Networks
• Constraint Satisfaction Problem Dichotomy for Finite Templates: a Proof Via Consistency Checks
• A polynomial-time algorithm for median-closed semilinear constraints
• A dichotomy theorem for nonuniform CSPs simplified
• Chromatic numbers of directed hypergraphs with no "bad" cycles
• A new algorithm for constraint satisfaction problems with few subpowers templates