DROPS

Document

DOI: 10.4230/LIPIcs.STACS.2021.10

Symmetric Promise Constraint Satisfaction Problems: Beyond the Boolean Case

Authors: Libor Barto, Diego Battistelli, and Kevin M. Berg

Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)

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."

Cite as

Libor Barto, Diego Battistelli, and Kevin M. Berg. Symmetric Promise Constraint Satisfaction Problems: Beyond the Boolean Case. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.STACS.2021.10},
  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}
}

Search Results

Documents authored by Berg, Kevin M.

Symmetric Promise Constraint Satisfaction Problems: Beyond the Boolean Case

Abstract

Cite as

Thanks for your feedback!

Could not send message