Topology and adjunction in promise constraint satisfaction
| Autor: | Andrei Krokhin, Jakub Opršal, Marcin Wrochna, Stanislav Živný |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2022 |
| Předmět: |
FOS: Computer and information sciences
Computer Science - Computational Complexity Computer Science - Logic in Computer Science Discrete Mathematics (cs.DM) General Computer Science General Mathematics Data_MISCELLANEOUS FOS: Mathematics Algebraic Topology (math.AT) Mathematics - Algebraic Topology Computational Complexity (cs.CC) Computer Science - Discrete Mathematics Logic in Computer Science (cs.LO) |
| Zdroj: | SIAM Journal on Computing, 2023, Vol.52(1), pp.38-79 [Peer Reviewed Journal] |
| DOI: | 10.1137/20m1378223 |
| Popis: | The approximate graph colouring problem, whose complexity is unresolved in most cases, concerns finding a $c$-colouring of a graph that is promised to be $k$-colourable, where $c\geq k$. This problem naturally generalises 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 analyse 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 colouring and promise graph homomorphism problems. Comment: This merges and subsumes arXiv:1904.03214 and arXiv:1907.00872. After reviews |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|