Andrei Krokhin, Durham University
"The complexity of valued constraint satisfaction problems"
The Valued Constraint Satisfaction Problem (VCSP) is a well-known combinatorial optimisation problem. An instance of VCSP is given by a finite set of variables, a finite domain of labels for the variables, and a sum of functions, each function depending on a subset of the variables. Each function can take finite rational values specifying costs of assignments of labels to its variables or the infinite value, which indicates an infeasible assignment. The goal is to find an assignment of labels to the variables that minimizes the sum. The case when all functions take only values 0 and infinity corresponds to the standard CSP. We study (assuming that P≠NP) how the computational complexity of VCSP depends on the set of functions allowed in the instances, the so-called constraint language. Helped greatly by algebra, massive progress has been made in the last three years on this complexity classification question, and our work gives the final answer to it.
This is joint work with Vladimir Kolmogorov and Michal Rolinek (both from IST Austria).
MC 5413