I will consider the Valued Constraint Satisfaction Problem (VCSP), whose goal is to minimize a sum of local terms where each term comes from a fixed set of functions (called a "language") over a fixed discrete domain. I will present recent results characterizing languages that can be solved using the basic LP relaxation. This includes languages consisting of submodular functions, as well as their generalizations.

One of such generalizations is k-submodular functions. In the second part of the talk I will present an application of such functions in computer vision.

Based on joint work with Igor Gridchyn, Andrei Krokhin, Michal Rolínek, Johann Thapper and Stanislav Živný: http://pub.ist.ac.at/~vnk/papers/BLP-JOURNAL.html http://pub.ist.ac.at/~vnk/papers/VCSP.html http://pub.ist.ac.at/~vnk/papers/POTTS.html