Binarisation for Valued Constraint Satisfaction Problems

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

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
• Public URL: https://durham-repository.worktribe.com/output/1348303
• Related Public URLs: https://arxiv.org/abs/1608.01628