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


Jakub Opršal

Marcin Wrochna

Stanislav Živný


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.


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.

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
Public URL
Related Public URLs


You might also like

Downloadable Citations