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 language | English |
---|---|
Pages (from-to) | 2279-2300 |
Number of pages | 22 |
Journal | SIAM Journal on Discrete Mathematics |
Volume | 31 |
Issue number | 4 |
Early online date | 3 Oct 2017 |
DOIs | |
Publication status | E-pub ahead of print - 3 Oct 2017 |