The complexity of finite-valued CSPs

Abstract

We study the computational complexity of exact minimisation of rational-valued discrete functions. Let $\Gamma$ be a set of rational-valued functions on a fixed finite domain; such a set is called a finite-valued constraint language. The valued constraint satisfaction problem, $\mathrm{VCSP}(\Gamma )$, is the problem of minimising a function given as a sum of functions from $\Gamma$. We establish a dichotomy theorem with respect to exact solvability for all finite-valued constraint languages defined on domains of arbitrary finite size. We show that every constraint language $\Gamma$ either admits a binary symmetric fractional polymorphism in which case the basic linear programming relaxation solves any instance of $\mathrm{VCSP}(\Gamma )$ exactly, or $\Gamma$ satisfies a simple hardness condition that allows for a polynomial-time reduction from Max-Cut to $\mathrm{VCSP}(\Gamma )$.

References in corpus (5)

• The Power of Linear Programming for Valued CSPs
• The power of linear programming for general-valued CSPs
• The complexity of conservative valued CSPs
• An Algebraic Theory of Complexity for Discrete Optimisation
• Hybrid tractability of soft constraint problems

Cited by in corpus (16)

• Algebraic approach to promise constraint satisfaction
• The power of Sherali-Adams relaxations for general-valued CSPs
• CLAP: A New Algorithm for Promise CSPs
• The limits of SDP relaxations for general-valued CSPs
• 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
• The complexity of general-valued CSPs seen from the other side
• The Power of Arc Consistency for CSPs Defined by Partially-Ordered Forbidden Patterns
• Super-Reparametrizations of Weighted CSPs: Properties and Optimization Perspective
• Computational Complexity of the Minimum Cost Homomorphism Problem on Three-Element Domains
• Hierarchies of Minion Tests for PCSPs through Tensors
• Pliability and Approximating Max-CSPs
• Using a min-cut generalisation to go beyond Boolean surjective VCSPs
• On Planar Valued CSPs
• An Application of Farkas' Lemma to Finite-Valued Constraint Satisfaction Problems over Infinite Domains