The complexity of finite-valued CSPs

Conference item

Let Γ be a set of rational-valued functions on a fixed finite domain; such a set is called a finite-valued constraint language. The valued constraint satisfaction problem, VCSP(Γ), is the problem of minimising a function given as a sum of functions from Γ. We establish a dichotomy theorem with respect to exact solvability for all finite-valued languages defined on domains of arbitrary finite size.

We show that every core language Γ either admits a binary idempotent and symmetric fractional polymorphism in which case the basic linear programming relaxation solves any instance of VCSP(Γ) exactly, or Γ satisfies a simple hardness condition that allows for a polynomial-time reduction from Max-Cut to VCSP(Γ). In other words, there is a single algorithm for all tractable cases and a single reason for intractability. Our results show that for exact solvability of VCSPs the basic linear programming relaxation suffices and semidefinite relaxations do not add any power. The proof uses a variation of Motzkin’s Transposition Theorem, hyperplane arrangements, and a technique recently introduced by Kolmogorov [arXiv:1207.7213] reformulated using Markov chains.

Our results generalise all previous partial classifications of finite-valued languages: the classifications of {0, 1}-valued languages on two-element, three-element, and four-element domains obtained by Creignou [JCSS’95], Jonsson et al. [SICOMP’06], and Jonsson et al. [CP’11], respectively; the classification of {0, 1}-valued languages containing all unary functions obtained by Deineko et al. [JACM’06]; the classifi- cations of finite-valued languages on two-element and threeelement domains obtained by Cohen et al. [AIJ’06] and Huber et al. [SODA’13], respectively; the classification of finite- valued languages containing all {0, 1}-valued unary functions obtained by Kolmogorov and Zivn´y [SODA’12]; and ˇthe classification of Min-0-Ext problems obtained recently by Hirai [SODA’13].

Authors: Thapper, J; Živný, S

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Association for Computing Machinery
• Host title: Proceedings of the 45th Annual ACM Symposium on Theory of Computing (STOC ’13)
• Journal: 45th Annual ACM Symposium on Theory of Computing
• Publication date: 2013-06-01
• DOI: 10.1145/2488608.2488697
• ISSN: 1557-735X, 0004-5411
• ISBN: 9781450320290
• Keywords: complexity; Discrete optimization; valued constraint satisfaction problems; dichotomy