Necessary Conditions for Tractability of Valued CSPs

DOI10.1137/140990346zbMath1347.08009arXiv1502.03482OpenAlexW1834711058MaRDI QIDQ3455247

Johan Thapper, Stanislav Živný

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

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

Related Items (5)

On planar valued CSPs ⋮ The Power of Sherali--Adams Relaxations for General-Valued CSPs ⋮ The Complexity of Valued CSPs ⋮ Backdoor Sets for CSP. ⋮ Representing Fitness Landscapes by Valued Constraints to Understand the Complexity of Local Search

Cites Work

• Colouring, constraint satisfaction, and complexity
• Maximal infinite-valued constraint languages
• On the complexity of H-coloring
• On the algebraic structure of combinatorial problems
• Boosting search with variable elimination in constraint optimization and constraint satisfaction problems
• The complexity of soft constraint satisfaction
• Minimal clones -- a minicourse
• The Approximability of Constraint Satisfaction Problems
• 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
• A Dichotomy Theorem for the General Minimum Cost Homomorphism Problem
• The Complexity of Finite-Valued CSPs
• Constraint Satisfaction Problems Solvable by Local Consistency Methods
• Skew Bisubmodularity and Valued CSPs
• Algebraic Properties of Valued Constraint Satisfaction Problem
• Sherali-Adams Relaxations for Valued CSPs
• The Maximum Solution Problem on Graphs
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• Principles of Constraint Programming
• Extensions of the Minimum Cost Homomorphism Problem
• MAX ONES Generalized to Larger Domains
• The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
• The structure of finite algebras
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Closure properties of constraints
• The Complexity of Valued Constraint Satisfaction Problems
• The complexity of maximal constraint languages
• The Power of Linear Programming for General-Valued CSPs
• The Complexity of General-Valued CSPs
• Classifying the Complexity of Constraints Using Finite Algebras
• The Power of Linear Programming for Finite-Valued CSPs: A Constructive Characterization
• The Complexity of Three-Element Min-Sol and Conservative Min-Cost-Hom
• The complexity of conservative valued CSPs
• An Algebraic Theory of Complexity for Discrete Optimization
• The complexity of satisfiability problems
• Introduction to the Maximum Solution Problem
• Algebras which are independently generated by every n elements
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Necessary Conditions for Tractability of Valued CSPs