The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side

DOI10.1137/19M1250121OpenAlexW4206989225MaRDI QIDQ5026391

Miguel Romero, Clément Carbonnel, Stanislav Živný

Publication date: 8 February 2022

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

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

zbMATH Keywords

treewidthvalued constraint satisfactionhomomorphism problemsfractional homomorphismSherali-Adams LP relaxation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) General topics of discrete mathematics in relation to computer science (68R01) Linear programming (90C05) Logic in computer science (03B70)

Related Items

PTAS for Sparse General-valued CSPs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Enumerating homomorphisms
• Containment of conjunctive queries on annotated relations
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• The core of a graph
• Graph minors. III. Planar tree-width
• Extended formulation for CSP that is compact for instances of bounded treewidth
• Graph minors. V. Excluding a planar graph
• Geometric algorithms and combinatorial optimization
• Graph searching and a min-max theorem for tree-width
• Boosting search with variable elimination in constraint optimization and constraint satisfaction problems
• Conjunctive-query containment and constraint satisfaction
• Networks of constraints: Fundamental properties and applications to picture processing
• Tree-width and the Sherali-Adams operator
• The complexity of soft constraint satisfaction
• Parametrized complexity theory.
• Nonserial dynamic programming
• Classification of annotation semirings over containment of conjunctive queries
• Complexity of conservative constraint satisfaction problems
• The Complexity of Finite-Valued CSPs
• Constraint Satisfaction Problems Solvable by Local Consistency Methods
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• Algebraic Properties of Valued Constraint Satisfaction Problem
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• 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)
• A Sufficient Condition for Backtrack-Free Search
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Fixed-Parameter Tractability and Completeness I: Basic Results
• A Proof of the CSP Dichotomy Conjecture
• The Complexity of General-Valued CSPs
• Classifying the Complexity of Constraints Using Finite Algebras
• The Power of Sherali--Adams Relaxations for General-Valued CSPs
• Bounded Tree-Width and CSP-Related Problems
• Tractability and Learnability Arising from Algebras with Few Subpowers
• Tractable Hypergraph Properties for Constraint Satisfaction and Conjunctive Queries
• On the Power of k-Consistency
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A Trichotomy in the Complexity of Counting Answers to Conjunctive Queries

This page was built for publication: The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side