Algebraic properties of valued constraint satisfaction problem

DOI10.1007/978-3-662-47672-7_69MaRDI QIDQ3448842zbMATH OpenOpenAlexFDO

Authors Marcin Kozik, Joanna Ochremiak

Publication date 27 October 2015

Published in Automata, Languages, and Programming (Search for Journal in Brave)

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

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) Computational aspects of satisfiability (68R07)

Abstract: The paper presents an algebraic framework for optimization problems expressible as Valued Constraint Satisfaction Problems. Our results generalize the algebraic framework for the decision version (CSPs) provided by Bulatov et al. [SICOMP 2005]. We introduce the notions of weighted algebras and varieties and use the Galois connection due to Cohen et al. [SICOMP 2013] to link VCSP languages to weighted algebras. We show that the difficulty of VCSP depends only on the weighted variety generated by the associated weighted algebra. Paralleling the results for CSPs we exhibit a reduction to cores and rigid cores which allows us to focus on idempotent weighted varieties. Further, we propose an analogue of the Algebraic CSP Dichotomy Conjecture; prove the hardness direction and verify that it agrees with known results for VCSPs on two-element sets [Cohen et al. 2006], finite-valued VCSPs [Thapper and Zivny 2013] and conservative VCSPs [Kolmogorov and Zivny 2013].

Recommendations

• An Algebraic Approach to Valued Constraint Satisfaction
• An algebraic theory of complexity for valued constraints: establishing a Galois connection
• A note on some collapse results of valued constraints
• The complexity of general-valued CSPs
• An algebraic theory of complexity for discrete optimization.

Cites work

• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• A remark on functionally free algebras
• Absorbing subalgebras, cyclic terms, and the constraint satisfaction problem
• An algebraic theory of complexity for discrete optimization.
• Classifying the Complexity of Constraints Using Finite Algebras
• Closure properties of constraints
• Complexity of conservative constraint satisfaction problems
• scientific article; zbMATH DE number 1670830 (Why is no real title available?)
• scientific article; zbMATH DE number 3751028 (Why is no real title available?)
• On the complexity of H-coloring
• Skew bisubmodularity and valued CSPs
• The complexity of conservative valued CSPs
• The complexity of satisfiability problems
• The complexity of soft constraint satisfaction
• The complexity of valued constraint satisfaction
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Universal algebra and hardness results for constraint satisfaction problems

Cited in

(31)

• On a general framework for network representability in discrete optimization
• Piecewise linear valued constraint satisfaction problems with fixed number of variables
• Using a Min-Cut generalisation to go beyond Boolean surjective VCSPs
• On planar valued CSPs
• An application of Farkas' lemma to finite-valued constraint satisfaction problems over infinite domains
• An algebraic theory of complexity for valued constraints: establishing a Galois connection
• A Galois connection for valued constraint languages of infinite size
• Sherali-Adams relaxations for valued CSPs
• Necessary conditions for tractability of valued CSPs
• The complexity of valued CSPs
• SMT solving for functional programming over infinite structures
• The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side
• Submodular functions and valued constraint satisfaction problems over infinite domains
• The combined basic LP and affine IP relaxation for promise VCSPs on infinite domains
• Beyond Boolean surjective VCSPs
• An Algebraic Approach to Valued Constraint Satisfaction
• The Complexity of Boolean Surjective General-Valued CSPs
• The complexity of general-valued CSPs
• The power of Sherali-Adams relaxations for general-valued CSPs
• Binarisation for valued constraint satisfaction problems
• An algebraic theory of complexity for discrete optimization.
• CLAP: A New Algorithm for Promise CSPs
• PTAS for Sparse General-valued CSPs
• Valued constraint satisfaction problems
• A topological version of Schaefer's dichotomy theorem
• The complexity of resilience problems via valued constraint satisfaction problems
• Algebraic approach to approximation
• The Sherali-Adams and Weisfeiler-Leman hierarchies in (promise valued) constraint satisfaction problems
• Temporal valued constraint satisfaction problems
• The complexity of resilience problems via valued constraint satisfaction
• A note on some collapse results of valued constraints

This page was built for publication: Algebraic properties of valued constraint satisfaction problem

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