Binarisation for valued constraint satisfaction problems
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 C...
| Main Authors: | , , , , , |
|---|---|
| Format: | Journal article |
| Published: |
Society for Industrial and Applied Mathematics
2017
|
| _version_ | 1811140570266992640 |
|---|---|
| author | Cohen, D Cooper, M Jeavons, P Krokhin, A Powell, R Zivny, S |
| author_facet | Cohen, D Cooper, M Jeavons, P Krokhin, A Powell, R Zivny, S |
| author_sort | Cohen, D |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-07T03:51:37Z |
| format | Journal article |
| id | oxford-uuid:c177c768-5e25-4bbe-b35d-201050a457b3 |
| institution | University of Oxford |
| last_indexed | 2024-09-25T04:24:05Z |
| publishDate | 2017 |
| publisher | Society for Industrial and Applied Mathematics |
| record_format | dspace |
| spelling | oxford-uuid:c177c768-5e25-4bbe-b35d-201050a457b32024-08-20T13:31:27ZBinarisation for valued constraint satisfaction problemsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:c177c768-5e25-4bbe-b35d-201050a457b3Symplectic Elements at OxfordSociety for Industrial and Applied Mathematics2017Cohen, DCooper, MJeavons, PKrokhin, APowell, RZivny, SWe 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. |
| spellingShingle | Cohen, D Cooper, M Jeavons, P Krokhin, A Powell, R Zivny, S Binarisation for valued constraint satisfaction problems |
| title | Binarisation for valued constraint satisfaction problems |
| title_full | Binarisation for valued constraint satisfaction problems |
| title_fullStr | Binarisation for valued constraint satisfaction problems |
| title_full_unstemmed | Binarisation for valued constraint satisfaction problems |
| title_short | Binarisation for valued constraint satisfaction problems |
| title_sort | binarisation for valued constraint satisfaction problems |
| work_keys_str_mv | AT cohend binarisationforvaluedconstraintsatisfactionproblems AT cooperm binarisationforvaluedconstraintsatisfactionproblems AT jeavonsp binarisationforvaluedconstraintsatisfactionproblems AT krokhina binarisationforvaluedconstraintsatisfactionproblems AT powellr binarisationforvaluedconstraintsatisfactionproblems AT zivnys binarisationforvaluedconstraintsatisfactionproblems |