2010/08/24 by Vladimir Kolmogorov, Kolmogorov, Vladimir · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Computer science #Constraint (computer-aided design) #Constraint Satisfaction and Optimization #Constraint satisfaction problem #Discrete mathematics #Domain (mathematical analysis) #FOS: Computer and information sciences #Finite set #Mathematics #Morphism #Set (abstract data type) #Unary operation #cs.CC
paper · pdf · doi:10.48550/arxiv.1008.4035
22 pages
arxiv created 2010/08/24 · openalex publication_date 2010/08/24 · arxiv updated 2010/08/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.