Skip to main content

Research Repository

Advanced Search

The Complexity of General-Valued CSPs

Kolmogorov, V.; Krokhin, A.; Rolinek, M.

The Complexity of General-Valued CSPs Thumbnail


Authors

V. Kolmogorov

M. Rolinek



Abstract

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. We study, assuming that P ≠ NP, how the complexity of this very general problem depends on the set of functions allowed in the instances, the so-called constraint language. The case when all allowed functions take values in {0, ∞} corresponds to ordinary CSPs, where one deals only with the feasibility issue and there is no optimization. This case is the subject of the Algebraic CSP Dichotomy Conjecture predicting for which constraint languages CSPs are tractable (i.e. solvable in polynomial time) and for which NP-hard. The case when all allowed functions take only finite values corresponds to finite-valued CSP, where the feasibility aspect is trivial and one deals only with the optimization issue. The complexity of finite-valued CSPs was fully classified by Thapper and Zivny. An algebraic necessary condition for tractability of a general-valued CSP with a fixed constraint language was recently given by Kozik and Ochremiak. As our main result, we prove that if a constraint language satisfies this algebraic necessary condition, and the feasibility CSP (i.e. the problem of deciding whether a given instance has a feasible solution) corresponding to the VCSP with this language is tractable, then the VCSP is tractable. The algorithm is a simple combination of the assumed algorithm for the feasibility CSP and the standard LP relaxation. As a corollary, we obtain that a dichotomy for ordinary CSPs would imply a dichotomy for general-valued CSPs.

Citation

Kolmogorov, V., Krokhin, A., & Rolinek, M. (2015). The Complexity of General-Valued CSPs. In 2015 IEEE 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2015) : Berkeley, California, USA, 17-20 October 2015 ; proceedings (1246-1258). https://doi.org/10.1109/focs.2015.80

Conference Name 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS)
Conference Location Berkeley
Acceptance Date Jun 22, 2015
Publication Date Oct 20, 2015
Deposit Date Mar 9, 2016
Publicly Available Date Mar 28, 2024
Pages 1246-1258
Series ISSN 0272-5428
Book Title 2015 IEEE 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2015) : Berkeley, California, USA, 17-20 October 2015 ; proceedings.
DOI https://doi.org/10.1109/focs.2015.80
Related Public URLs http://arxiv.org/abs/1502.07327

Files

Accepted Conference Proceeding (312 Kb)
PDF

Copyright Statement
© 2015 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.





You might also like



Downloadable Citations