Cohen, D. and Cooper, M. and Jeavons, P. and Krokhin, A. and Powell, R. and Zivny, S. (2017) 'Binarisation for valued constraint satisfaction problems.', SIAM journal on discrete mathematics., 31 (4). pp. 2279-2300.
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.
| Item Type: | Article |
|---|---|
| Full text: | (AM) Accepted Manuscript Download PDF (297Kb) |
| Full text: | (VoR) Version of Record Download PDF (325Kb) |
| Status: | Peer-reviewed |
| Publisher Web site: | https://doi.org/10.1137/16M1088107 |
| Publisher statement: | © 2017, Society for Industrial and Applied Mathematics |
| Date accepted: | 24 July 2017 |
| Date deposited: | 12 October 2017 |
| Date of first online publication: | 03 October 2017 |
| Date first made open access: | No date available |
Save or Share this output
| Export: | |
| Look up in GoogleScholar |
