The complexity of finite-valued CSPs

18^th February 2014, 16:00 Ashton Lecture Theater
Dr Stanislav Zivny
Computer Science
Oxford University

Abstract

Let L be a set of rational-valued functions on a fixed finite domain; such a set
is called a finite-valued constraint language. We are interested in the problem
of minimising a function given explicitly as a sum of functions from L. We
establish a dichotomy theorem with respect to exact solvability for all
finite-valued languages defined on domains of arbitrary finite size. We present
a simple algebraic condition that characterises the tractable cases. Moreover,
we show that a single algorithm based on linear programming solves all tractable
cases. Furthermore, we show that there is a single reason for intractability;
namely, a very specific reduction from Max-Cut.

(based on work published at FOCS'12 and STOC'13, joint work with J. Thapper)