The complexity of finite-valued CSPsReportar como inadecuado

The complexity of finite-valued CSPs - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Reference: Thapper, J and Zivny, S, The complexity of finite-valued CSPs. Journal of the ACM, 63 (4).Citable link to this page:


The complexity of finite-valued CSPs

Abstract: We study the computational complexity of exact minimisation of separable rational-valued discretefunctions. Let Γ be a set of rational-valued functions on a fixed finite domain; such a set is called a finite-valuedconstraint language. The valued constraint satisfaction problem, VCSP (Γ), is the problem of minimisinga function given as a sum of functions from Γ. We establish a dichotomy theorem with respect to exactsolvability 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 inwhich case the basic linear programming relaxation solves any instance of VCSP(Γ) exactly, or Γ satisfies asimple hardness condition that allows for a polynomial-time reduction from Max-Cut to VCSP(Γ).

Peer Review status:Peer reviewedPublication status:PublishedVersion:Accepted manuscriptNotes:Copyright 2016 ACM. This is the author accepted manuscript version of the article. The final version may be available online from the Association for Computing Machinery at

Bibliographic Details

Publisher: Association for Computing Machinery

Publisher Website:

Journal: Journal of the ACMsee more from them

Publication Website:

Volume: 63

Extent: Article No. 37Identifiers

Urn: uuid:9030708d-1cf0-435f-80ad-d591addd1668


Source identifier: 574782

Issn: 1535-9921 Item Description

Type: Journal article;

Version: Accepted manuscript Tiny URL: pubs:574782


Autor: Thapper, J - grantNumberFP7-2007-2013 Grant Agreement no. 257039 fundingEuropean Research Council - - - Zivny, S - institutionUni



Documentos relacionados