Binarisation for Valued Constraint Satisfaction Problems

Binarisation for Valued Constraint Satisfaction Problems

Show other versions (1)

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

Full description

Bibliographic Details
Main Authors: Cohen, D, Cooper, M, Jeavons, P, Krokhin, A, Powell, R, Zivny, S
Format: Journal article
Published: 2016
Description
Summary: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 Bulin et al. [LMCS'15] 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.

Similar Items