Preliminary version appeared in

We study the complexity of valued constraint satisfaction problems (VCSP). A
problem from VCSP is characterised by a *constraint language*, a fixed set
of cost functions over a finite domain. An instance of the problem is specified
by a sum of cost functions from the language and the goal is to minimise the
sum. Under the unique games conjecture, the approximability of finite-valued
VCSPs is well-understood, see Raghavendra [FOCS'08]. However, there is no
characterisation of finite-valued VCSPs, let alone general-valued VCSPs, that
can be solved exactly in polynomial time, thus giving insights from a
combinatorial optimisation perspective.

We consider the case of languages containing all possible unary cost functions.
In the case of languages consisting of only {0,∞}-valued cost functions
(i.e. relations), such languages have been called *conservative* and
studied by Bulatov [LICS'03] and recently by Barto [LICS'11]. Since we study
valued languages, we call a language *conservative* if it contains all
finite-valued unary cost functions.
The computational complexity of conservative valued languages has been studied
by Cohen et al. [AIJ'06] for languages over Boolean domains, by Deineko et al.
[JACM'08] for {0,1}-valued languages (a.k.a Max-CSP), and by Takhanov
[STACS'10] for {0,∞}-valued languages containing all finite-valued
unary cost functions (a.k.a. Min-Cost-Hom).

We prove a Schaefer-like dichotomy theorem for conservative valued languages: if
all cost functions in the language satisfy a certain condition (specified by a
complementary combination of *STP and MJN multimorphisms*), then any
instance can be solved in polynomial time (via a new algorithm developed in this
paper), otherwise the language is NP-hard. This is the *first* complete
complexity classification of *general-valued constraint languages* over
non-Boolean domains. It is a common phenomenon that complexity classifications
of problems over non-Boolean domains is significantly harder than the Boolean
case. The polynomial-time algorithm we present for the tractable cases is a
generalisation of the submodular minimisation problem and a result of
Cohen et al. [TCS'08].

Our results generalise previous results by Takhanov [STACS'10] and (a subset of
results) by Cohen et al. [AIJ'06] and Deineko et al. [JACM'08]. Moreover, our
results do not rely on any computer-assisted search as in Deineko et al. [JACM'08], and provide a powerful tool for proving hardness of finite-valued and
general-valued languages.

doi

Extended abstract (SODA)