Skip to main content

Research Repository

Advanced Search

Algebraic approach to promise constraint satisfaction

Bulin, J.; Krokhin, A.; Oprsal, J.

Algebraic approach to promise constraint satisfaction Thumbnail


Authors

J. Bulin

J. Oprsal



Abstract

The complexity and approximability of the constraint satisfaction problem (CSP) has been actively studied over the last 20 years. A new version of the CSP, the promise CSP (PCSP) has recently been proposed, motivated by open questions about the approximability of variants of satisfiability and graph colouring. The PCSP significantly extends the standard decision CSP. The complexity of CSPs with a fixed constraint language on a finite domain has recently been fully classified, greatly guided by the algebraic approach, which uses polymorphisms — high-dimensional symmetries of solution spaces — to analyse the complexity of problems. The corresponding classification for PCSPs is wide open and includes some long-standing open questions, such as the complexity of approximate graph colouring, as special cases. The basic algebraic approach to PCSP was initiated by Brakensiek and Guruswami, and in this paper we significantly extend it and lift it from concrete properties of polymorphisms to their abstract properties. We introduce a new class of problems that can be viewed as algebraic versions of the (Gap) Label Cover problem, and show that every PCSP with a fixed constraint language is equivalent to a problem of this form. This allows us to identify a “measure of symmetry” that is well suited for comparing and relating the complexity of different PCSPs via the algebraic approach. We demonstrate how our theory can be applied by improving the state-of-the-art in approximate graph colouring: we show that, for any k ≥ 3, it is NP-hard to find a (2k − 1)-colouring of a given k-colourable graph.

Citation

Bulin, J., Krokhin, A., & Oprsal, J. (2019). Algebraic approach to promise constraint satisfaction. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC 2019) (602-613). https://doi.org/10.1145/3313276.3316300

Conference Name ACM Symposium on Theory of Computing (STOC)
Conference Location Phoenix, USA
Acceptance Date Apr 23, 2019
Online Publication Date Jun 23, 2019
Publication Date Apr 23, 2019
Deposit Date Apr 23, 2019
Publicly Available Date Jun 23, 2019
Volume 2019
Pages 602-613
Series ISSN 0737-8017
Book Title Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC 2019).
DOI https://doi.org/10.1145/3313276.3316300

Files

Accepted Conference Proceeding (853 Kb)
PDF

Copyright Statement
© ACM 2019. This is the author's version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, https://doi.org/10.1145/10.1145/3313276.3316300







You might also like



Downloadable Citations