Topology and adjunction in promise constraint satisfaction

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

doi:10.1137/20m1378223

Topology and adjunction in promise constraint satisfaction

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

Authors

Professor Andrei Krokhin andrei.krokhin@durham.ac.uk
Professor

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