Binarisation for Valued Constraint Satisfaction Problems

Abstract

We study methods for transforming valued constraint satisfaction problems (VCSPs) to binary VCSPs. First, we show that the standard dual encoding preserves many aspects of the algebraic properties that capture the computational complexity of VCSPs. Second, we extend the reduction of CSPs to binary CSPs described by Bulin et al. [LMCS'15] to VCSPs. This reduction establishes that VCSPs over a fixed valued constraint language are polynomial-time equivalent to Minimum-Cost Homomorphism Problems over a fixed digraph.

arXiv commentSubsumes 1507.01776

References in corpus (6)

• The power of linear programming for general-valued CSPs
• The Expressive Power of Binary Submodular Functions
• An Algebraic Theory of Complexity for Discrete Optimisation
• The power of Sherali-Adams relaxations for general-valued CSPs
• Binary Encodings of Non-binary Constraint Satisfaction Problems: Algorithms and Experimental Results
• Maltsev digraphs have a majority polymorphism