Binarisation for Valued Constraint Satisfaction Problems

Cohen, D.; Cooper, M.; Jeavons, P.; Krokhin, A.; Powell, R.; Zivny, S.

doi:10.1137/16m1088107

Binarisation for Valued Constraint Satisfaction Problems

Cohen, D.; Cooper, M.; Jeavons, P.; Krokhin, A.; Powell, R.; Zivny, S.

Authors

D. Cohen

M. Cooper

P. Jeavons

Professor Andrei Krokhin andrei.krokhin@durham.ac.uk
Professor

Dr Rob Powell robert.powell@durham.ac.uk
Assistant Professor

S. Zivny

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.

Citation

Cohen, D., Cooper, M., Jeavons, P., Krokhin, A., Powell, R., & Zivny, S. (2017). Binarisation for Valued Constraint Satisfaction Problems. SIAM Journal on Discrete Mathematics, 31(4), 2279-2300. https://doi.org/10.1137/16m1088107

Journal Article Type	Article
Acceptance Date	Jul 24, 2017
Online Publication Date	Oct 3, 2017
Publication Date	Oct 3, 2017
Deposit Date	Sep 28, 2017
Publicly Available Date	Oct 12, 2017
Journal	SIAM Journal on Discrete Mathematics
Print ISSN	0895-4801
Electronic ISSN	1095-7146
Publisher	Society for Industrial and Applied Mathematics
Peer Reviewed	Peer Reviewed
Volume	31
Issue	4
Pages	2279-2300
DOI	https://doi.org/10.1137/16m1088107
Related Public URLs	https://arxiv.org/abs/1608.01628