A dichotomy theorem for conservative general-valued CSPs

الأصل · EN

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. We consider the case of so-called conservative languages; that is, languages containing all unary cost functions, thus allowing arbitrary restrictions on the domains of the variables. We prove a Schaefer-like dichotomy theorem for this case: 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 by the algorithm of Kolmogorov and Zivny (arXiv:1008.3104v1), otherwise the language is NP-hard. This generalises recent results of Takhanov (STACS'10) who considered {0,∞}-valued languages containing additionally all finite-valued unary cost functions, and Kolmogorov and Zivny (arXiv:1008.1555v1) who considered finite-valued conservative languages.