The complexity of conservative valued CSPs

DOI10.1145/2450142.2450146MaRDI QIDQ5395709zbMATH OpenOpenAlexFDO

Authors Vladimir Kolmogorov, S. Zivny

Publication date 17 February 2014

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1110.2809

zbMATH Keywords

complexitydichotomydiscrete optimizationmultimorphismssubmodularityvalued constraint satisfaction problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27)

Abstract: 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.

Recommendations

• The complexity of conservative valued CSPs
• The complexity of general-valued CSPs
• The power of linear programming for general-valued CSPs

Cited in

(31)

• On planar valued CSPs
• Tractability in constraint satisfaction problems: a survey
• Minimum cost homomorphisms with constrained costs
• A complexity classification of spin systems with an external field
• Computational complexity of the extended minimum cost homomorphism problem on three-element domains
• Min CSP on four elements: moving beyond submodularity
• Algebraic properties of valued constraint satisfaction problem
• Sherali-Adams relaxations for valued CSPs
• Necessary conditions for tractability of valued CSPs
• Extensions of the minimum cost homomorphism problem
• On Planar Valued CSPs
• Hybrid tractable classes of constraint problems
• Backdoor sets for CSP
• The complexity of valued CSPs
• Testing the Complexity of a Valued CSP Language
• The Complexity of Boolean Surjective General-Valued CSPs
• Hybrid VCSPs with crisp and valued conservative templates
• Representing fitness landscapes by valued constraints to understand the complexity of local search
• The Complexity of Boolean Surjective General-Valued CSPs
• The power of linear programming for general-valued CSPs
• The complexity of general-valued CSPs
• The power of Sherali-Adams relaxations for general-valued CSPs
• Binarisation for valued constraint satisfaction problems
• An algebraic theory of complexity for discrete optimization.
• The complexity of conservative valued CSPs
• Discrete convexity and polynomial solvability in minimum 0-extension problems
• Hybrid tractability of valued constraint problems
• Generalisations of matrix partitions: complexity and obstructions
• Generalized minimum 0-extension problem and discrete convexity
• List homomorphisms by deleting edges and vertices: tight complexity bounds for bounded-treewidth graphs
• The complexity of approximating conservative counting CSPs

This page was built for publication: The complexity of conservative valued CSPs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5395709)