Algebraic Properties of Valued Constraint Satisfaction Problem

Abstract

The paper presents an algebraic framework for optimization problems expressible as Valued Constraint Satisfaction Problems. Our results generalize the algebraic framework for the decision version (CSPs) provided by Bulatov et al. [SICOMP 2005]. We introduce the notions of weighted algebras and varieties and use the Galois connection due to Cohen et al. [SICOMP 2013] to link VCSP languages to weighted algebras. We show that the difficulty of VCSP depends only on the weighted variety generated by the associated weighted algebra. Paralleling the results for CSPs we exhibit a reduction to cores and rigid cores which allows us to focus on idempotent weighted varieties. Further, we propose an analogue of the Algebraic CSP Dichotomy Conjecture; prove the hardness direction and verify that it agrees with known results for VCSPs on two-element sets [Cohen et al. 2006], finite-valued VCSPs [Thapper and Zivny 2013] and conservative VCSPs [Kolmogorov and Zivny 2013].

arXiv admin note: text overlap with arXiv:1207.6692 by other authors

Cited by in corpus (8)

• The combined basic LP and affine IP relaxation for promise VCSPs on infinite domains
• The complexity of Boolean surjective general-valued CSPs
• A Galois Connection for Weighted (Relational) Clones of Infinite Size
• Sherali-Adams relaxations for valued CSPs
• PTAS for Sparse General-Valued CSPs
• Piecewise Linear Valued CSPs Solvable by Linear Programming Relaxation
• On a general framework for network representability in discrete optimization
• Using a min-cut generalisation to go beyond Boolean surjective VCSPs