Binarisation for valued constraint satisfaction problems

DOI10.1137/16M1088107MaRDI QIDQ5371026zbMATH OpenOpenAlexFDO

Authors

Publication date 24 October 2017

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

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

zbMATH Keywords

discrete optimizationpolymorphismsvalued constraint satisfaction problemsfractional polymorphisms

Mathematics Subject Classification ID

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

Abstract: We study methods for transforming valued constraint satisfaction problems (VCSPs) to binary VCSPs. First, we show that the standard dual encoding preserves many aspects of the algebraic properties that capture the computational complexity of VCSPs. Second, we extend the reduction of CSPs to binary CSPs described by Bulin et al. [LMCS'15] to VCSPs. This reduction establishes that VCSPs over a fixed valued constraint language are polynomial-time equivalent to Minimum-Cost Homomorphism Problems over a fixed digraph.

Recommendations

• An Algebraic Approach to Valued Constraint Satisfaction
• A note on some collapse results of valued constraints
• The complexity of valued CSPs

Cites work

• scientific article; zbMATH DE number 2243365 (Why is no real title available?)
• scientific article; zbMATH DE number 2243409 (Why is no real title available?)
• A Galois connection for valued constraint languages of infinite size
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• A Simple Algorithm for Mal'tsev Constraints
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• A dichotomy for minimum cost graph homomorphisms
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• A dichotomy theorem for the general minimum cost homomorphism problem
• A finer reduction of constraint problems to digraphs
• Algebraic properties of valued constraint satisfaction problem
• An algebraic theory of complexity for discrete optimization.
• Binary vs. non-binary constraints
• Bounded width problems and algebras
• Classifying the Complexity of Constraints Using Finite Algebras
• Closure properties of constraints
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• 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
• Existence theorems for weakly symmetric operations
• Extensions of the minimum cost homomorphism problem
• Finitely related algebras in congruence distributive varieties have near unanimity terms
• Graphs of relational structures: restricted types
• Maltsev digraphs have a majority polymorphism
• Markov random fields for vision and image processing
• Networks of constraints: Fundamental properties and applications to picture processing
• On digraph coloring problems and treewidth duality
• On the complexity of H-coloring
• Robustly solvable constraint satisfaction problems
• Skew bisubmodularity and valued CSPs
• The Complexity of Three-Element Min-Sol and Conservative Min-Cost-Hom
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The complexity of conservative valued CSPs
• The complexity of general-valued CSPs
• The complexity of satisfiability problems
• The complexity of valued CSPs
• The dichotomy of minimum cost homomorphism problems for digraphs
• The expressive power of binary submodular functions
• The expressive power of valued constraints: Hierarchies and collapses
• The power of Sherali-Adams relaxations for general-valued CSPs
• The power of linear programming for general-valued CSPs
• The wonderland of reflections
• Tractability and learnability arising from algebras with few subpowers
• Tree clustering for constraint networks

Cited in

(6)

• Beyond JWP: a tractable class of binary VCSPs via M-convex intersection
• An Algebraic Approach to Valued Constraint Satisfaction
• scientific article; zbMATH DE number 7561584 (Why is no real title available?)
• The power of Sherali-Adams relaxations for general-valued CSPs
• A tractable class of binary VCSPs via M-convex intersection
• Galois connections for patterns: an algebra of labelled graphs

This page was built for publication: Binarisation for valued constraint satisfaction problems

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