Necessary conditions for tractability of valued CSPs

DOI10.1137/140990346MaRDI QIDQ3455247zbMATH OpenOpenAlexFDO

Authors Johan Thapper, S. Zivny

Publication date 4 December 2015

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

discrete optimizationvalued constraint satisfaction problemsweighted clonesweighted polymorphisms

Mathematics Subject Classification ID

Applications of universal algebra in computer science (08A70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Abstract: The connection between constraint languages and clone theory has been a fruitful line of research on the complexity of constraint satisfaction problems. In a recent result, Cohen et al. [SICOMP'13] have characterised a Galois connection between valued constraint languages and so-called weighted clones. In this paper, we study the structure of weighted clones. We extend the results of Creed and Zivny from [CP'11/SICOMP'13] on types of weightings necessarily contained in every nontrivial weighted clone. This result has immediate computational complexity consequences as it provides necessary conditions for tractability of weighted clones and thus valued constraint languages. We demonstrate that some of the necessary conditions are also sufficient for tractability, while others are provably not.

Recommendations

• A Galois connection for valued constraint languages of infinite size
• An algebraic theory of complexity for valued constraints: establishing a Galois connection
• A Galois connection for weighted (relational) clones of infinite size
• An algebraic theory of complexity for discrete optimization.
• The complexity of general-valued CSPs

Cites work

• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• A dichotomy theorem for the general minimum cost homomorphism problem
• Algebraic properties of valued constraint satisfaction problem
• Algebras which are independently generated by every n elements
• An algebraic theory of complexity for discrete optimization.
• Boosting search with variable elimination in constraint optimization and constraint satisfaction problems
• Classifying the Complexity of Constraints Using Finite Algebras
• Closure properties of constraints
• Colouring, constraint satisfaction, and complexity
• Complexity classifications of Boolean constraint satisfaction problems
• Complexity of conservative constraint satisfaction problems
• Computational complexity of the extended minimum cost homomorphism problem on three-element domains
• Constraint Satisfaction Problems Solvable by Local Consistency Methods
• Extensions of the minimum cost homomorphism problem
• scientific article; zbMATH DE number 3972929 (Why is no real title available?)
• scientific article; zbMATH DE number 3987347 (Why is no real title available?)
• scientific article; zbMATH DE number 193411 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Introduction to the Maximum Solution Problem
• MAX ONES Generalized to Larger Domains
• Maximal infinite-valued constraint languages
• Minimal clones -- a minicourse
• On the algebraic structure of combinatorial problems
• On the complexity of H-coloring
• Principles of Constraint Programming
• Sherali-Adams relaxations for valued CSPs
• Skew bisubmodularity and valued CSPs
• The approximability of constraint satisfaction problems
• The complexity of conservative valued CSPs
• The complexity of general-valued CSPs
• The complexity of maximal constraint languages
• The complexity of satisfiability problems
• The complexity of soft constraint satisfaction
• The Complexity of Three-Element Min-Sol and Conservative Min-Cost-Hom
• The complexity of valued constraint satisfaction
• The complexity of valued constraint satisfaction problems
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
• The Maximum Solution Problem on Graphs
• The Power of Linear Programming for Finite-Valued CSPs: A Constructive Characterization
• The power of linear programming for general-valued CSPs
• The structure of finite algebras
• Universal algebra and applications in theoretical computer science

Cited in

(8)

• On planar valued CSPs
• A Galois connection for valued constraint languages of infinite size
• On Planar Valued CSPs
• A Galois connection for weighted (relational) clones of infinite size
• Backdoor sets for CSP
• The complexity of valued CSPs
• Representing fitness landscapes by valued constraints to understand the complexity of local search
• The power of Sherali-Adams relaxations for general-valued CSPs

This page was built for publication: Necessary conditions for tractability of valued CSPs

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