The complexity of conservative valued CSPs

V. Kolmogorov, S. Živný, in:, SIAM, 2012, pp. 750–759.

Conference Paper | Published
Kolmogorov, VladimirIST Austria; Živný, Stanislav
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.
Publishing Year
Date Published
Vladimir Kolmogorov is supported by the Royal Academy of Eng ineering/EPSRC.
750 - 759
SODA: Symposium on Discrete Algorithms

Cite this

Kolmogorov V, Živný S. The complexity of conservative valued CSPs. In: SIAM; 2012:750-759.
Kolmogorov, V., & Živný, S. (2012). The complexity of conservative valued CSPs (pp. 750–759). Presented at the SODA: Symposium on Discrete Algorithms, SIAM.
Kolmogorov, Vladimir, and Stanislav Živný. “The Complexity of Conservative Valued CSPs,” 750–59. SIAM, 2012.
V. Kolmogorov and S. Živný, “The complexity of conservative valued CSPs,” presented at the SODA: Symposium on Discrete Algorithms, 2012, pp. 750–759.
Kolmogorov V, Živný S. 2012. The complexity of conservative valued CSPs. SODA: Symposium on Discrete Algorithms 750–759.
Kolmogorov, Vladimir, and Stanislav Živný. The Complexity of Conservative Valued CSPs. SIAM, 2012, pp. 750–59.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access


Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar