We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Topology and adjunction in promise constraint satisfaction

Krokhin, Andrei and Opršal, Jakub and Wrochna, Marcin and Živný, Stanislav (2023) 'Topology and adjunction in promise constraint satisfaction.', SIAM Journal on Computing, 52 (1). pp. 38-79.


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.

Item Type:Article
Full text:Publisher-imposed embargo
(AM) Accepted Manuscript
File format - PDF
Publisher Web site:
Date accepted:23 September 2022
Date deposited:06 December 2022
Date of first online publication:No date available
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar