In SIAM Journal on Computing (SICOMP), 44(1):1-36, 2015.

Abstract

Let $D$, called the domain, be a fixed finite set and let $\Gamma$,
called the valued constraint language, be a fixed set of functions of the
form $f:D^m\to\mathbb{Q}\cup\{\infty\}$, where different functions might have
different arity $m$. We study the valued constraint satisfaction problem
parametrised by $\Gamma$, denoted by VCSP$(\Gamma)$. These are minimisation
problems given by $n$ variables and the objective function given by a sum of
functions from $\Gamma$, each depending on a subset of the $n$ variables.
For example, if $D=\{0,1\}$ and $\Gamma$ contains all ternary $\{0,\infty\}$-valued
functions, VCSP($\Gamma$) corresponds to 3-SAT.
More generally, if $\Gamma$ contains only $\{0,\infty\}$-valued functions,
VCSP($\Gamma$) corresponds to
CSP($\Gamma$).
If $D=\{0,1\}$ and $\Gamma$ contains all ternary $\{0,1\}$-valued
functions, VCSP($\Gamma$) corresponds to Min-3-SAT, in which the goal is to
minimise the number of unsatisfied clauses in a 3-CNF instance.
Finite-valued constraint languages contain functions that take on
only rational values and not infinite values.

Our main result is a precise algebraic characterisation of valued constraint
languages whose instances can be solved exactly by the basic linear
programming relaxation (BLP). For a valued constraint language
$\Gamma$, BLP is a decision procedure for $\Gamma$ if and only if $\Gamma$
admits a symmetric fractional polymorphism of every arity.
For a finite-valued constraint language $\Gamma$, BLP is a decision procedure if
and only if $\Gamma$ admits a symmetric fractional polymorphism of some
arity, or equivalently, if $\Gamma$ admits a symmetric fractional polymorphism
of arity 2.

Using these results, we obtain tractability of several novel classes of problems, including problems over valued constraint
languages that are: (1) submodular on arbitrary lattices; (2)
$k$-submodular on arbitrary finite domains;
(3) weakly (and hence strongly) tree-submodular on arbitrary trees.