The power of Sherali-Adams relaxations for general-valued CSPs

Abstract

We give a precise algebraic characterisation of the power of Sherali-Adams relaxations for solvability of valued constraint satisfaction problems to optimality. The condition is that of bounded width which has already been shown to capture the power of local consistency methods for decision CSPs and the power of semidefinite programming for robust approximation of CSPs. Our characterisation has several algorithmic and complexity consequences. On the algorithmic side, we show that several novel and many known valued constraint languages are tractable via the third level of the Sherali-Adams relaxation. For the known languages, this is a significantly simpler algorithm than the previously obtained ones. On the complexity side, we obtain a dichotomy theorem for valued constraint languages that can express an injective unary function. This implies a simple proof of the dichotomy theorem for conservative valued constraint languages established by Kolmogorov and Zivny [JACM'13], and also a dichotomy theorem for the exact solvability of Minimum-Solution problems. These are generalisations of Minimum-Ones problems to arbitrary finite domains. Our result improves on several previous classifications by Khanna et al. [SICOMP'00], Jonsson et al. [SICOMP'08], and Uppman [ICALP'13].

Full version of an ICALP'15 paper (arXiv:1502.05301)

References in corpus (6)

• The power of linear programming for general-valued CSPs
• Necessary conditions for tractability of valued CSPs
• A Galois Connection for Weighted (Relational) Clones of Infinite Size
• An Effective Fusion Technique of Cloud Computing and Networking Series
• A Reduction from Valued CSP to Min Cost Homomorphism Problem for Digraphs
• Graphs of relational structures: restricted types

Cited by in corpus (12)

• The Power of the Combined Basic LP and Affine Relaxation for Promise CSPs
• CLAP: A New Algorithm for Promise CSPs
• Local consistency as a reduction between constraint satisfaction problems
• The limits of SDP relaxations for general-valued CSPs
• The combined basic LP and affine IP relaxation for promise VCSPs on infinite domains
• A Galois Connection for Weighted (Relational) Clones of Infinite Size
• The complexity of general-valued CSPs seen from the other side
• Binarisation for Valued Constraint Satisfaction Problems
• Using a min-cut generalisation to go beyond Boolean surjective VCSPs
• Hierarchies of Minion Tests for PCSPs through Tensors
• 1-in-3 vs. Not-All-Equal: Dichotomy of a broken promise
• On Planar Valued CSPs