Algebraic Properties of Valued Constraint Satisfaction Problem

Joanna Ochremiak ( University of Warsaw )

We present an algebraic framework for optimization problems expressible as Valued Constraint Satisfaction Problems (VCSPs). Our results generalize the algebraic framework for the decision version (CSPs) provided by Bulatov et al. We introduce the notion of a weighted algebra, and use the Galois connection due to Cohen et al. to link VCSP languages to weighted algebras. Paralleling the results for CSPs we exhibit a reduction to cores and rigid cores which allows us to focus on idempotent weighted algebras. Further, we propose an analogue of the Algebraic CSP Dichotomy Conjecture, and prove the hardness direction establishing a necessary algebraic condition for tractability of VCSPs with fixed constraint languages.

Joint work with Marcin Kozik.