The complexity of general-valued constraint satisfaction problems seen from the other side
The constraint satisfaction problem (CSP) is concerned with homomorphisms between two structures. For CSPs with restricted left-hand-side structures, the results of Dalmau, Kolaitis, and Vardi [Proceedings of the 8th International Conference on Principles and Practice of Constraint Programming, Spri...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Society for Industrial and Applied Mathematics
2022
|
| _version_ | 1797107848321171456 |
|---|---|
| author | Carbonnel, C Romero, M Živný, S |
| author_facet | Carbonnel, C Romero, M Živný, S |
| author_sort | Carbonnel, C |
| collection | OXFORD |
| description | The constraint satisfaction problem (CSP) is concerned with homomorphisms between two structures. For CSPs with restricted left-hand-side structures, the results of Dalmau, Kolaitis, and Vardi [Proceedings of the 8th International Conference on Principles and Practice of Constraint Programming, Springer, New York, 2002, pp. 310--326], Grohe [J. ACM, 54 (2007), 1], and Atserias, Bulatov, and Dalmau [Proceedings of the 34th International Colloquium on Automata, Languages and Programming, Springer, New York, 2007, pp. 279--290] establish the precise borderline of polynomial-time solvability (subject to complexity-theoretic assumptions) and of solvability by bounded-consistency algorithms (unconditionally) as bounded treewidth modulo homomorphic equivalence. The general-valued constraint satisfaction problem (VCSP) is a generalization of the CSP concerned with homomorphisms between two valued structures. For VCSPs with restricted left-hand-side valued structures, we establish the precise borderline of polynomial-time solvability (subject to complexity-theoretic assumptions) and of solvability by the 𝑘th level of the Sherali--Adams LP hierarchy (unconditionally). We also obtain results on related problems concerned with finding a solution and recognizing the tractable cases; the latter has an application in database theory. |
| first_indexed | 2024-03-07T07:21:24Z |
| format | Journal article |
| id | oxford-uuid:7d400e93-a7a2-44e2-914f-596bb8d583d7 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T07:21:24Z |
| publishDate | 2022 |
| publisher | Society for Industrial and Applied Mathematics |
| record_format | dspace |
| spelling | oxford-uuid:7d400e93-a7a2-44e2-914f-596bb8d583d72022-10-13T09:36:32ZThe complexity of general-valued constraint satisfaction problems seen from the other sideJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:7d400e93-a7a2-44e2-914f-596bb8d583d7EnglishSymplectic ElementsSociety for Industrial and Applied Mathematics2022Carbonnel, CRomero, MŽivný, SThe constraint satisfaction problem (CSP) is concerned with homomorphisms between two structures. For CSPs with restricted left-hand-side structures, the results of Dalmau, Kolaitis, and Vardi [Proceedings of the 8th International Conference on Principles and Practice of Constraint Programming, Springer, New York, 2002, pp. 310--326], Grohe [J. ACM, 54 (2007), 1], and Atserias, Bulatov, and Dalmau [Proceedings of the 34th International Colloquium on Automata, Languages and Programming, Springer, New York, 2007, pp. 279--290] establish the precise borderline of polynomial-time solvability (subject to complexity-theoretic assumptions) and of solvability by bounded-consistency algorithms (unconditionally) as bounded treewidth modulo homomorphic equivalence. The general-valued constraint satisfaction problem (VCSP) is a generalization of the CSP concerned with homomorphisms between two valued structures. For VCSPs with restricted left-hand-side valued structures, we establish the precise borderline of polynomial-time solvability (subject to complexity-theoretic assumptions) and of solvability by the 𝑘th level of the Sherali--Adams LP hierarchy (unconditionally). We also obtain results on related problems concerned with finding a solution and recognizing the tractable cases; the latter has an application in database theory. |
| spellingShingle | Carbonnel, C Romero, M Živný, S The complexity of general-valued constraint satisfaction problems seen from the other side |
| title | The complexity of general-valued constraint satisfaction problems seen from the other side |
| title_full | The complexity of general-valued constraint satisfaction problems seen from the other side |
| title_fullStr | The complexity of general-valued constraint satisfaction problems seen from the other side |
| title_full_unstemmed | The complexity of general-valued constraint satisfaction problems seen from the other side |
| title_short | The complexity of general-valued constraint satisfaction problems seen from the other side |
| title_sort | complexity of general valued constraint satisfaction problems seen from the other side |
| work_keys_str_mv | AT carbonnelc thecomplexityofgeneralvaluedconstraintsatisfactionproblemsseenfromtheotherside AT romerom thecomplexityofgeneralvaluedconstraintsatisfactionproblemsseenfromtheotherside AT zivnys thecomplexityofgeneralvaluedconstraintsatisfactionproblemsseenfromtheotherside AT carbonnelc complexityofgeneralvaluedconstraintsatisfactionproblemsseenfromtheotherside AT romerom complexityofgeneralvaluedconstraintsatisfactionproblemsseenfromtheotherside AT zivnys complexityofgeneralvaluedconstraintsatisfactionproblemsseenfromtheotherside |