Paper detail

The complexity of finite-valued CSPs

We study the computational complexity of exact minimisation of rational-valued discrete functions. Let $Γ$ 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, $\operatorname{VCSP}(Γ)$, is the problem of minimising a function given as a sum of functions from $Γ$. 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 $Γ$ either admits a binary symmetric fractional polymorphism in which case the basic linear programming relaxation solves any instance of $\operatorname{VCSP}(Γ)$ exactly, or $Γ$ satisfies a simple hardness condition that allows for a polynomial-time reduction from Max-Cut to $\operatorname{VCSP}(Γ)$.