---
res:
  bibo_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.@eng
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Vladimir
      foaf_name: Kolmogorov, Vladimir
      foaf_surname: Kolmogorov
      foaf_workInfoHomepage: http://www.librecat.org/personId=3D50B0BA-F248-11E8-B48F-1D18A9856A87
  - foaf_Person:
      foaf_givenName: Andrei
      foaf_name: Krokhin, Andrei
      foaf_surname: Krokhin
  - foaf_Person:
      foaf_givenName: Michal
      foaf_name: Rolinek, Michal
      foaf_surname: Rolinek
      foaf_workInfoHomepage: http://www.librecat.org/personId=3CB3BC06-F248-11E8-B48F-1D18A9856A87
  bibo_doi: 10.1109/FOCS.2015.80
  dct_date: 2015^xs_gYear
  dct_identifier:
  - UT:000379204700071
  dct_language: eng
  dct_publisher: IEEE@
  dct_title: The complexity of general-valued CSPs@
...