Answers are grounded in this paper and cite their sources.
We study the computational complexity of exact minimization 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, VCSP(Γ), is the problem of minimizing 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 VCSP(Γ) exactly, or Γ satisfies a simple hardness condition that allows for a polynomial-time reduction from Max-Cut to VCSP(Γ).
No takes yet. Share an insight, caveat, or question.
Thapper et al. (2016) studied this question.
Synapse has enriched one related paper. Consider it for comparative context: