Journal article
Binarisation for valued constraint satisfaction problems
- 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. [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.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Accepted manuscript, pdf, 376.2KB, Terms of use)
-
- Publisher copy:
- 10.1137/16M1088107
Authors
+ Engineering and Physical Sciences Research Council
More from this funder
- Funding agency for:
- Jeavons, P
- Zivny, S
- Grant:
- EP/L021226/1
- Publisher:
- Society for Industrial and Applied Mathematics
- Journal:
- SIAM Journal on Discrete Mathematics More from this journal
- Volume:
- 31
- Issue:
- 4
- Pages:
- 2279–2300
- Publication date:
- 2017-10-03
- Acceptance date:
- 2017-07-24
- DOI:
- EISSN:
-
1095-7146
- ISSN:
-
0895-4801
- Keywords:
- Pubs id:
-
pubs:709082
- UUID:
-
uuid:c177c768-5e25-4bbe-b35d-201050a457b3
- Local pid:
-
pubs:709082
- Source identifiers:
-
709082
- Deposit date:
-
2017-07-24
- ARK identifier:
Terms of use
- Copyright holder:
- Society for Industrial and Applied Mathematics
- Copyright date:
- 2017
- Notes:
- Copyright © 2017 Society for Industrial and Applied Mathematics. This is the accepted manuscript version of the article. The final version is available online from SIAM at: https://doi.org/10.1137/16M1088107
If you are the owner of this record, you can report an update to it here: Report update to this record