Abstract: 
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 finitevalued VCSPs is wellunderstood, see Raghavendra [FOCS’08]. However, there is no characterisation of finitevalued VCSPs, let alone generalvalued 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 finitevalued 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 MaxCSP), and by Takhanov [STACS’10] for {0,∞}valued languages containing all finite valued unary cost functions (a.k.a. MinCostHom).
We prove a Schaeferlike 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 NPhard. This is the first complete complexity classification of generalvalued constraint languages over nonBoolean domains. It is a common phenomenon that complexity classifications of problems over nonBoolean domains is significantly harder than the Boolean case. The polynomialtime 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 computerassisted search as in Deineko et al. [JACM’08], and provide a powerful tool for proving hardness of finitevalued and generalvalued languages.
