The power of linear programming for general-valued CSPs

Vladimir Kolmogorov, Johan Thapper and Stanislav Zivny.

In SIAM Journal on Computing (SICOMP), 44(1):1-36, 2015.


Abstract

Let $D$, called the domain, be a fixed finite set and let $\Gamma$, called the valued constraint language, be a fixed set of functions of the form $f:D^m\to\mathbb{Q}\cup\{\infty\}$, where different functions might have different arity $m$. We study the valued constraint satisfaction problem parametrised by $\Gamma$, denoted by VCSP$(\Gamma)$. These are minimisation problems given by $n$ variables and the objective function given by a sum of functions from $\Gamma$, each depending on a subset of the $n$ variables. For example, if $D=\{0,1\}$ and $\Gamma$ contains all ternary $\{0,\infty\}$-valued functions, VCSP($\Gamma$) corresponds to 3-SAT. More generally, if $\Gamma$ contains only $\{0,\infty\}$-valued functions, VCSP($\Gamma$) corresponds to CSP($\Gamma$). If $D=\{0,1\}$ and $\Gamma$ contains all ternary $\{0,1\}$-valued functions, VCSP($\Gamma$) corresponds to Min-3-SAT, in which the goal is to minimise the number of unsatisfied clauses in a 3-CNF instance. Finite-valued constraint languages contain functions that take on only rational values and not infinite values.

Our main result is a precise algebraic characterisation of valued constraint languages whose instances can be solved exactly by the basic linear programming relaxation (BLP). For a valued constraint language $\Gamma$, BLP is a decision procedure for $\Gamma$ if and only if $\Gamma$ admits a symmetric fractional polymorphism of every arity. For a finite-valued constraint language $\Gamma$, BLP is a decision procedure if and only if $\Gamma$ admits a symmetric fractional polymorphism of some arity, or equivalently, if $\Gamma$ admits a symmetric fractional polymorphism of arity 2.

Using these results, we obtain tractability of several novel classes of problems, including problems over valued constraint languages that are: (1) submodular on arbitrary lattices; (2) $k$-submodular on arbitrary finite domains; (3) weakly (and hence strongly) tree-submodular on arbitrary trees.


Links

doi arXiv version