The Complexity of Finite-Valued CSPs

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 m...

Full description

Saved in:
Bibliographic Details
Published in:Journal of the ACM 2016-11, Vol.63 (4), p.1-33
Main Authors: Thapper, Johan, Zivny, Stanislav
Format: Article
Language:English
Subjects:
BASIC (programming language)
Complexity
Computational Complexity
Computer Science
Data Structures and Algorithms
Dichotomies
Discrete Mathematics
Hardness
Linear programming
Logic in Computer Science
Mathematical analysis
Mathematical models
Optimization
Polynomials
Studies
Theorems
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 all finite-valued constraint languages defined on domains of 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(Γ).
ISSN:0004-5411
1557-735X
DOI:10.1145/2974019