---
_id: '644'
abstract:
- lang: eng
  text: 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 6=
    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 f0;1g 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 they are NP-hard. The case when all allowed functions take only finite
    values corresponds to a finitevalued 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 Živný. 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.
article_processing_charge: No
arxiv: 1
author:
- first_name: Vladimir
  full_name: Kolmogorov, Vladimir
  id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
  last_name: Kolmogorov
- first_name: Andrei
  full_name: Krokhin, Andrei
  last_name: Krokhin
- first_name: Michal
  full_name: Rolinek, Michal
  id: 3CB3BC06-F248-11E8-B48F-1D18A9856A87
  last_name: Rolinek
citation:
  ama: Kolmogorov V, Krokhin A, Rolinek M. The complexity of general-valued CSPs.
    <i>SIAM Journal on Computing</i>. 2017;46(3):1087-1110. doi:<a href="https://doi.org/10.1137/16M1091836">10.1137/16M1091836</a>
  apa: Kolmogorov, V., Krokhin, A., &#38; Rolinek, M. (2017). The complexity of general-valued
    CSPs. <i>SIAM Journal on Computing</i>. SIAM. <a href="https://doi.org/10.1137/16M1091836">https://doi.org/10.1137/16M1091836</a>
  chicago: Kolmogorov, Vladimir, Andrei Krokhin, and Michal Rolinek. “The Complexity
    of General-Valued CSPs.” <i>SIAM Journal on Computing</i>. SIAM, 2017. <a href="https://doi.org/10.1137/16M1091836">https://doi.org/10.1137/16M1091836</a>.
  ieee: V. Kolmogorov, A. Krokhin, and M. Rolinek, “The complexity of general-valued
    CSPs,” <i>SIAM Journal on Computing</i>, vol. 46, no. 3. SIAM, pp. 1087–1110,
    2017.
  ista: Kolmogorov V, Krokhin A, Rolinek M. 2017. The complexity of general-valued
    CSPs. SIAM Journal on Computing. 46(3), 1087–1110.
  mla: Kolmogorov, Vladimir, et al. “The Complexity of General-Valued CSPs.” <i>SIAM
    Journal on Computing</i>, vol. 46, no. 3, SIAM, 2017, pp. 1087–110, doi:<a href="https://doi.org/10.1137/16M1091836">10.1137/16M1091836</a>.
  short: V. Kolmogorov, A. Krokhin, M. Rolinek, SIAM Journal on Computing 46 (2017)
    1087–1110.
date_created: 2018-12-11T11:47:40Z
date_published: 2017-06-29T00:00:00Z
date_updated: 2025-09-23T13:45:56Z
day: '29'
department:
- _id: VlKo
doi: 10.1137/16M1091836
ec_funded: 1
external_id:
  arxiv:
  - '1502.07327'
  isi:
  - '000404774300010'
intvolume: '        46'
isi: 1
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1502.07327
month: '06'
oa: 1
oa_version: Preprint
page: 1087 - 1110
project:
- _id: 25FBA906-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '616160'
  name: 'Discrete Optimization in Computer Vision: Theory and Practice'
publication: SIAM Journal on Computing
publication_status: published
publisher: SIAM
publist_id: '7138'
quality_controlled: '1'
related_material:
  record:
  - id: '1637'
    relation: other
    status: public
scopus_import: '1'
status: public
title: The complexity of general-valued CSPs
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 46
year: '2017'
...