Skip to main content

Research Repository

Advanced Search

Topology and adjunction in promise constraint satisfaction

Krokhin, Andrei; Opršal, Jakub; Wrochna, Marcin; Živný, Stanislav

Topology and adjunction in promise constraint satisfaction Thumbnail


Authors

Jakub Opršal

Marcin Wrochna

Stanislav Živný



Abstract

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≥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.

Citation

Krokhin, A., Opršal, J., Wrochna, M., & Živný, S. (2023). Topology and adjunction in promise constraint satisfaction. SIAM Journal on Computing, 52(1), 38-79. https://doi.org/10.1137/20m1378223

Journal Article Type Article
Acceptance Date Sep 23, 2022
Online Publication Date Feb 14, 2023
Publication Date Feb 28, 2023
Deposit Date Dec 6, 2022
Publicly Available Date Mar 31, 2023
Journal SIAM Journal on Computing
Print ISSN 0097-5397
Electronic ISSN 1095-7111
Publisher Society for Industrial and Applied Mathematics
Peer Reviewed Peer Reviewed
Volume 52
Issue 1
Pages 38-79
DOI https://doi.org/10.1137/20m1378223
Public URL https://durham-repository.worktribe.com/output/1185729
Related Public URLs https://arxiv.org/abs/2003.11351
https://ora.ox.ac.uk/objects/uuid:17b6e233-14e7-4904-825c-56fec49f8af8

Files





You might also like



Downloadable Citations