Algebraic Necessary Condition for Tractability of Valued CSP

Many natural optimisation problems are expressible as Valued Constraint Satisfaction Problems (VCSPs). Examples include: Max-Cut, Minimum Vertex Cover, Max-3-Sat. We present an algebraic framework for VCSPs, generalising the algebraic framework for its decision version (CSPs) provided by Bulatov et al. We formulate an Algebraic VCSP Dichotomy Conjecture, which says that each valued constraint language gives rise to an optimisation problem solvable in PTime, or to an NP-hard one. It also proposes a criterion to distinguish those two cases. We prove the hardness direction, establishing a necessary algebraic condition for tractability of VCSPs with fixed constraint languages. This is joint work with Marcin Kozik.

Authors

• Joanna Ochremiak

Keywords

No keywords are indexed for this paper.