Binarisation for Valued Constraint Satisfaction Problems. / Cohen, David; Zivny, Stanislav; Cooper, Martin; Jeavons, Peter; Krokhin, Andrei; Robert, Powell.

In: SIAM Journal on Discrete Mathematics, Vol. 31, No. 4, 27.10.2017, p. 2279-2300.

Research output: Contribution to journalArticle

Published

Documents

  • 1608.01628

    Accepted author manuscript, 296 KB, PDF-document

  • 16m1088107

    Final published version, 279 KB, PDF-document

    Licence: Not specified

  • David Cohen
  • Stanislav Zivny
  • Martin Cooper
  • Peter Jeavons
  • Andrei Krokhin
  • Powell Robert

Abstract

We study methods for transforming valued constraint satisfaction problems (VCSPs) to binary VCSPs. First, we show that the standard dual encoding preserves many aspects of the algebraic properties that capture the computational complexity of VCSPs. Second, we extend the reduction of CSPs to binary CSPs described by Bulín et al. [Log. Methods Comput. Sci., 11 (2015)] to VCSPs. This reduction establishes that VCSPs over a fixed valued constraint language are polynomial-time equivalent to minimum-cost homomorphism problems over a fixed digraph.
Original languageEnglish
Pages (from-to)2279-2300
Number of pages22
JournalSIAM Journal on Discrete Mathematics
Volume31
Issue number4
Early online date3 Oct 2017
DOIs
StatePublished - 27 Oct 2017
This open access research output is licenced under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

ID: 28605186