A dichotomy theorem for conservative general-valued CSPs

Computer Science – Computational Complexity

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

22 pages

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 so-called \emph{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 \emph{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,\infty\}$-valued languages containing additionally all finite-valued unary cost functions, and Kolmogorov and Zivny (arXiv:1008.1555v1) who considered \emph{finite-valued} conservative languages.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

A dichotomy theorem for conservative general-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 A dichotomy theorem for conservative general-valued CSPs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A dichotomy theorem for conservative general-valued CSPs will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-393858

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.