License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2021.10
URN: urn:nbn:de:0030-drops-136557
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13655/
Barto, Libor ;
Battistelli, Diego ;
Berg, Kevin M.
Symmetric Promise Constraint Satisfaction Problems: Beyond the Boolean Case
Abstract
The Promise Constraint Satisfaction Problem (PCSP) is a recently introduced vast generalization of the Constraint Satisfaction Problem (CSP). We investigate the computational complexity of a class of PCSPs beyond the most studied cases - approximation variants of satisfiability and graph coloring problems. We give an almost complete classification for the class of PCSPs of the form: given a 3-uniform hypergraph that has an admissible 2-coloring, find an admissible 3-coloring, where admissibility is given by a ternary symmetric relation. The only PCSP of this sort whose complexity is left open in this work is a natural hypergraph coloring problem, where admissibility is given by the relation "if two colors are equal, then the remaining one is higher."
BibTeX - Entry
@InProceedings{barto_et_al:LIPIcs.STACS.2021.10,
author = {Barto, Libor and Battistelli, Diego and Berg, Kevin M.},
title = {{Symmetric Promise Constraint Satisfaction Problems: Beyond the Boolean Case}},
booktitle = {38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
pages = {10:1--10:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-180-1},
ISSN = {1868-8969},
year = {2021},
volume = {187},
editor = {Bl\"{a}ser, Markus and Monmege, Benjamin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13655},
URN = {urn:nbn:de:0030-drops-136557},
doi = {10.4230/LIPIcs.STACS.2021.10},
annote = {Keywords: constraint satisfaction problems, promise constraint satisfaction, Boolean PCSP, polymorphism}
}
Keywords: |
|
constraint satisfaction problems, promise constraint satisfaction, Boolean PCSP, polymorphism |
Collection: |
|
38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021) |
Issue Date: |
|
2021 |
Date of publication: |
|
10.03.2021 |