The power of linear programming for finite-valued CSPs: a constructive characterization

Vladimir Kolmogorov.

In International Colloquium on Automata, Languages and Programming (ICALP), July 2013.


A class of valued constraint satisfaction problems (VCSPs) is characterised by a valued constraint language, a fixed set of cost functions on a finite domain. An instance of the problem is specified by a sum of cost functions from the language with the goal to minimise the sum.

We study which classes of finite-valued languages can be solved exactly by the basic linear programming relaxation (BLP). Recently, Thapper and Zivny showed [17] that if BLP solves the language then the language admits a binary commutative fractional polymorphism. We prove that the converse is also true. This leads to a necessary and a sufficient condition which can be checked in polynomial time for a given language. In contrast, the previous necessary and sufficient condition due to [17] involved infinitely many inequalities.



arXiv version

Superseded by the following paper:
The power of linear programming for general-valued CSPs.
Vladimir Kolmogorov, Johan Thapper and Stanislav Zivny.
arXiv , November 2013. (Submitted to a journal.)