The Complexity of General-Valued CSPs

DOI10.1137/16M1091836zbMath1371.68117arXiv1502.07327OpenAlexW2613504727MaRDI QIDQ5283238

Vladimir Kolmogorov, Andrei A. Krokhin, Michal Rolínek

Publication date: 21 July 2017

Published in: SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

complexitydichotomyvalued constraint satisfaction problemfractional polymorphism

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

Tractability in constraint satisfaction problems: a survey, CLAP: A New Algorithm for Promise CSPs, Necessary Conditions for Tractability of Valued CSPs, The lattice and semigroup structure of multipermutations, Towards a characterization of constant-factor approximable finite-valued CSPs, Beyond JWP: A Tractable Class of Binary VCSPs via M-Convex Intersection., Sparsification of Binary CSPs, The Power of Sherali--Adams Relaxations for General-Valued CSPs, PTAS for Sparse General-valued CSPs, Tractability of explaining classifier decisions, Unnamed Item, The Complexity of Boolean Surjective General-Valued CSPs, Binarisation for Valued Constraint Satisfaction Problems, Using a Min-Cut generalisation to go beyond Boolean surjective VCSPs, Unnamed Item, Unnamed Item, Unnamed Item, Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs, Sparsification of Binary CSPs, A Tractable Class of Binary VCSPs via M-Convex Intersection, Piecewise linear valued constraint satisfaction problems with fixed number of variables, Testing the Complexity of a Valued CSP Language, The Complexity of Quantified Constraints Using the Algebraic Formulation, The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side, The Complexity of Quantified Constraints: Collapsibility, Switchability, and the Algebraic Formulation

Uses Software

• JBool

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the algebraic structure of combinatorial problems
• Conjunctive-query containment and constraint satisfaction
• Networks of constraints: Fundamental properties and applications to picture processing
• Complexity of constraints. An overview of current research themes
• Supermodular functions and the complexity of MAX CSP
• The complexity of soft constraint satisfaction
• Complexity Classifications of Boolean Constraint Satisfaction Problems
• Robustly Solvable Constraint Satisfaction Problems
• The collapse of the bounded width hierarchy
• Absorbing Subalgebras, Cyclic Terms, and the Constraint Satisfaction Problem
• 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
• Min CSP on Four Elements: Moving beyond Submodularity
• Approximate Constraint Satisfaction Requires Large LP Relaxations
• The Complexity of Finite-Valued CSPs
• Constraint Satisfaction Problems Solvable by Local Consistency Methods
• Algebraic Properties of Valued Constraint Satisfaction Problem
• Sherali-Adams Relaxations for Valued CSPs
• The approximability of MAX CSP with fixed-value constraints
• Effectiveness of Structural Restrictions for Hybrid CSPs
• An Algebraic Characterisation of Complexity for Valued Constraint
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• Graphical Models, Exponential Families, and Variational Inference
• Tractable Optimization Problems through Hypergraph-Based Structural Restrictions
• The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Closure properties of constraints
• Correlation Decay and Tractability of CSPs.
• A Galois Connection for Weighted (Relational) Clones of Infinite Size
• The Complexity of Valued CSPs
• The Power of Linear Programming for General-Valued CSPs
• Classifying the Complexity of Constraints Using Finite Algebras
• The Complexity of Three-Element Min-Sol and Conservative Min-Cost-Hom
• The Power of Sherali--Adams Relaxations for General-Valued CSPs
• Tractability and Learnability Arising from Algebras with Few Subpowers
• The complexity of conservative valued CSPs
• Tractable Hypergraph Properties for Constraint Satisfaction and Conjunctive Queries
• An Algebraic Theory of Complexity for Discrete Optimization
• The complexity of satisfiability problems
• The Approximability of Three-valued MAX CSP
• Introduction to the Maximum Solution Problem
• Local Distribution and the Symmetry Gap: Approximability of Multiway Partitioning Problems
• Every 2-CSP allows nontrivial approximation