Topology and adjunction in promise constraint satisfaction
The approximate graph coloring problem, whose complexity is unresolved in most cases, concerns finding a c-coloring of a graph that is promised to be k-colorable, where c≥k. This problem naturally generalizes to promise graph homomorphism problems and further to promise constraint satisfaction probl...
| Main Authors: | , , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Society for Industrial and Applied Mathematics
2023
|
| _version_ | 1797108753036738560 |
|---|---|
| author | Krokhin, A Oprsal, J Wrochna, M Zivny, S |
| author_facet | Krokhin, A Oprsal, J Wrochna, M Zivny, S |
| author_sort | Krokhin, A |
| collection | OXFORD |
| description | The approximate graph coloring problem, whose complexity is unresolved in most cases, concerns finding a c-coloring of a graph that is promised to be k-colorable, where c≥k. This problem naturally generalizes to promise graph homomorphism problems and further to promise constraint satisfaction problems. The complexity of these problems has recently been studied through an algebraic approach. In this paper, we introduce two new techniques to analyze the complexity of promise CSPs: one is based on topology and the other on adjunction. We apply these techniques, together with the previously introduced algebraic approach, to obtain new unconditional NP-hardness results for a significant class of approximate graph coloring and promise graph homomorphism problems. |
| first_indexed | 2024-03-07T07:32:53Z |
| format | Journal article |
| id | oxford-uuid:17b6e233-14e7-4904-825c-56fec49f8af8 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T07:32:53Z |
| publishDate | 2023 |
| publisher | Society for Industrial and Applied Mathematics |
| record_format | dspace |
| spelling | oxford-uuid:17b6e233-14e7-4904-825c-56fec49f8af82023-02-17T08:03:15ZTopology and adjunction in promise constraint satisfactionJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:17b6e233-14e7-4904-825c-56fec49f8af8EnglishSymplectic ElementsSociety for Industrial and Applied Mathematics2023Krokhin, AOprsal, JWrochna, MZivny, SThe approximate graph coloring problem, whose complexity is unresolved in most cases, concerns finding a c-coloring of a graph that is promised to be k-colorable, where c≥k. This problem naturally generalizes to promise graph homomorphism problems and further to promise constraint satisfaction problems. The complexity of these problems has recently been studied through an algebraic approach. In this paper, we introduce two new techniques to analyze the complexity of promise CSPs: one is based on topology and the other on adjunction. We apply these techniques, together with the previously introduced algebraic approach, to obtain new unconditional NP-hardness results for a significant class of approximate graph coloring and promise graph homomorphism problems. |
| spellingShingle | Krokhin, A Oprsal, J Wrochna, M Zivny, S Topology and adjunction in promise constraint satisfaction |
| title | Topology and adjunction in promise constraint satisfaction |
| title_full | Topology and adjunction in promise constraint satisfaction |
| title_fullStr | Topology and adjunction in promise constraint satisfaction |
| title_full_unstemmed | Topology and adjunction in promise constraint satisfaction |
| title_short | Topology and adjunction in promise constraint satisfaction |
| title_sort | topology and adjunction in promise constraint satisfaction |
| work_keys_str_mv | AT krokhina topologyandadjunctioninpromiseconstraintsatisfaction AT oprsalj topologyandadjunctioninpromiseconstraintsatisfaction AT wrochnam topologyandadjunctioninpromiseconstraintsatisfaction AT zivnys topologyandadjunctioninpromiseconstraintsatisfaction |