Topology and adjunction in promise constraint satisfaction

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

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