Speaker: Vladimir Kolmogorov (Institute of Science and Technology Austria),

Abstract

Classifying complexity of different classes of optimization problems is an important research direction in Theoretical Computer Science. One prominent framework is Valued Constraint Satisfaction Problems (VCSPs) in which the class is parameterized by a ``language'' $\Gamma$, i.e.\ a set of cost functions over a fixed discrete domain $D$. A instance of VCSP($\Gamma$) is an arbitrary sum of functions from Gamma (possibly with overlapping variables), and the goal is to minimize the sum. The complexity of VCSP($\Gamma$) depends on how ``rich'' the set $\Gamma$ is. If, for example, $\Gamma$ contains only submodular functions then any instance in VCSP($\Gamma$) can be solved in polynomial time. If, on the other hand, $\Gamma$ contains e.g.\ the ``not-equal'' relation then VCSP($\Gamma$) can express the $|D|$-coloring problem and thus is NP-hard when $|D|>2$.

I will show that establishing complexity classification for plain CSPs (i.e.\ when functions in $\Gamma$ only take values in $\{0,\infty\}$) would immediately give the classification for general VCSPs. The key algorithmic tool that we use is a certain LP relaxation of the problem combined with the assumed algorithm for plain CSPs.

In the second part of the talk I will consider a version where we additionally restrict the structure of the instance to be \emph{planar}. More specifically, I will describe a generalization of the Edmonds's blossom-shrinking algorithm from ``perfect matching'' constraints to arbitrary ``even $\mbox{$\Delta$-matroid}$'' constraints. As a consequence of this, we settle the complexity classification of planar Boolean CSPs started by Dvořák and Kupec.

Based on joint work with Alexandr Kazda, Andrei Krokhin, Michal Rolínek, Johann Thapper and Stanislav Živný.