### The Complexity of Finite-Valued CSPsThe Complexity of Finite-Valued CSPs

Access Restriction
Subscribed

 Author Thapper, Johan ♦ Ivn, Stanislav Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2016 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Discrete optimization ♦ Complexity ♦ Dichotomy ♦ Valued constraint satisfaction problems Abstract We study the computational complexity of exact minimization of rational-valued discrete functions. 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 minimizing a function given as a sum of functions from Γ. We establish a dichotomy theorem with respect to exact solvability for $\textit{all}$ finite-valued constraint languages defined on domains of $\textit{arbitrary}$ finite size. We show that every constraint language Γ either admits a binary 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(Γ). Description Author Affiliation: University of Oxford, Oxford, United Kingdom (ivn, Stanislav); Université Paris-Est Marne-la-Vallée, France (Thapper, Johan) ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2016-09-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 63 Issue Number 4 Page Count 33 Starting Page 1 Ending Page 33

#### Open content in new tab

Source: ACM Digital Library