Titre :   Linear programming and the complexity of finite-valued CSPs

Exposant : Johan Thapper

Résumé : I will present a complete complexity classification for the finite-valued constraint satisfaction problem (VCSP). The VCSP can be seen as minimisation of separable functions, that is, the objective function is given as a sum of bounded-arity functions. Our result gives a dichotomy between problems satisfying a submodularity-like condition which are solvable in polynomial time by a linear programming relaxation, and NP-hard problems. The result generalises a host of partial classifications spanning the last 15 years.
This is joint work with Standa Zivny (Warwick, UK).