The complexity of general-valued CSPs

An instance of the Valued Constraint Satisfaction Problem (VCSP) is given by a finite set of variables, a finite domain of labels, and a sum of functions, each function depending on a subset of the variables. Each function can take finite 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 complexity of VCSP depends on the set of functions allowed in the instances, the so-called constraint language. Massive progress has been made in the last three years on this complexity classification question, and our work gives, in a way, the final answer to it, modulo the complexity of CSPs.

This is joint work with Vladimir Kolmogorov and Michal Rolinek (both from IST Austria).