Computer Science – Computational Complexity
Scientific paper
2011-10-12
Computer Science
Computational Complexity
38 pages. Full version of the paper that will appear in SODA 12
Scientific paper
We study the complexity of valued constraint satisfaction problems (VCSP). A problem from VCSP is characterised by a \emph{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 languages containing all possible unary cost functions. In the case of languages consisting of only $\{0,\infty\}$-valued cost functions (i.e. relations), such languages have been called \emph{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 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,\infty\}$-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 \emph{STP and MJN multimorphisms}), then any instance can be solved in polytime (via a new algorithm developed in this paper), otherwise the language is NP-hard. This is the \emph{first} complete complexity classification of \emph{general-valued constraint languages} over non-Boolean domains. This generalises 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- and general-valued languages.
Kolmogorov Vladimir
Zivny Stanislav
No associations
LandOfFree
The complexity of conservative valued CSPs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The complexity of conservative valued CSPs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The complexity of conservative valued CSPs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-498360