Document Open Access Logo

Symmetric Promise Constraint Satisfaction Problems: Beyond the Boolean Case

Authors Libor Barto , Diego Battistelli, Kevin M. Berg

PDF
Thumbnail PDF

File

LIPIcs.STACS.2021.10.pdf
  • Filesize: 2.73 MB
  • 16 pages

Document Identifiers

Author Details

Libor Barto
  • Department of Algebra, Faculty of Mathematics and Physics, Charles University, Prague, Czech Republic
Diego Battistelli
  • Department of Algebra, Faculty of Mathematics and Physics, Charles University, Prague, Czech Republic
Kevin M. Berg
  • Department of Algebra, Faculty of Mathematics and Physics, Charles University, Prague, Czech Republic

Funding

All three authors have received funding from the European Research Council (ERC) under the European Unions Horizon 2020 research and innovation programme (grant agreement No 771005).

Cite AsGet BibTex

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)
https://doi.org/10.4230/LIPIcs.STACS.2021.10

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

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
Keywords
  • constraint satisfaction problems
  • promise constraint satisfaction
  • Boolean PCSP
  • polymorphism

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Per Austrin, Venkatesan Guruswami, and Johan Håstad. (2+ε)-Sat is NP-hard. SIAM J. Comput., 46(5):1554-1573, 2017. URL: https://doi.org/10.1137/15M1006507.
  2. L. Barto. Promises make finite (constraint satisfaction) problems infinitary. In 2019 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 1-8, 2019. Google Scholar
  3. Libor Barto, Jakub Bulín, Andrei Krokhin, and Jakub Opršal. Algebraic approach to promise constraint satisfaction, 2019. URL: http://arxiv.org/abs/1811.00970.
  4. Libor Barto, Andrei Krokhin, and Ross Willard. Polymorphisms, and how to use them. In Andrei Krokhin and Stanislav Živný, editors, The Constraint Satisfaction Problem: Complexity and Approximability, volume 7 of Dagstuhl Follow-Ups, pages 1-44. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2017. URL: https://doi.org/10.4230/DFU.Vol7.15301.1.
  5. Libor Barto, Jakub Opršal, and Michael Pinsker. The wonderland of reflections. Israel Journal of Mathematics, 223(1):363-398, February 2018. URL: https://doi.org/10.1007/s11856-017-1621-9.
  6. Joshua Brakensiek and Venkatesan Guruswami. Promise constraint satisfaction: Structure theory and a symmetric boolean dichotomy. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'18, pages 1782-1801, Philadelphia, PA, USA, 2018. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=3174304.3175422.
  7. Joshua Brakensiek and Venkatesan Guruswami. Symmetric polymorphisms and efficient decidability of promise CSPs. In Proceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '20, page 297–304, USA, 2020. Society for Industrial and Applied Mathematics. Google Scholar
  8. Joshua Brakensiek, Venkatesan Guruswami, Marcin Wrochna, and Stanislav Živný. The power of the combined basic linear programming and affine relaxation for promise constraint satisfaction problems. SIAM Journal on Computing, 49(6):1232-1248, 2020. URL: https://doi.org/10.1137/20M1312745.
  9. Alex Brandts, Marcin Wrochna, and Stanislav Živný. The Complexity of Promise SAT on Non-Boolean Domains. In Artur Czumaj, Anuj Dawar, and Emanuela Merelli, editors, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), volume 168 of Leibniz International Proceedings in Informatics (LIPIcs), pages 17:1-17:13, Dagstuhl, Germany, 2020. Schloss Dagstuhl-Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.ICALP.2020.17.
  10. Andrei Bulatov, Peter Jeavons, and Andrei Krokhin. Classifying the complexity of constraints using finite algebras. SIAM J. Comput., 34(3):720-742, March 2005. URL: https://doi.org/10.1137/S0097539700376676.
  11. Andrei A. Bulatov. A dichotomy theorem for nonuniform CSPs. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 319-330, October 2017. URL: https://doi.org/10.1109/FOCS.2017.37.
  12. Jakub Bulín, Andrei Krokhin, and Jakub Opršal. Algebraic approach to promise constraint satisfaction. In Proceedings of the 51st Annual ACM SIGACT Symposium on the Theory of Computing (STOC ’19), New York, NY, USA, 2019. ACM. URL: https://doi.org/10.1145/3313276.3316300.
  13. Irit Dinur, Oded Regev, and Clifford Smyth. The hardness of 3-uniform hypergraph coloring. Combinatorica, 25(5):519-535, September 2005. URL: https://doi.org/10.1007/s00493-005-0032-4.
  14. Miron Ficak, Marcin Kozik, Miroslav Olsák, and Szymon Stankiewicz. Dichotomy for Symmetric Boolean PCSPs. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132 of Leibniz International Proceedings in Informatics (LIPIcs), pages 57:1-57:12, Dagstuhl, Germany, 2019. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.57.
  15. Pavol Hell and Jaroslav Nešetřil. On the complexity of H-coloring. J. Combin. Theory Ser. B, 48(1):92-110, 1990. Google Scholar
  16. Peter Jeavons. On the algebraic structure of combinatorial problems. Theor. Comput. Sci., 200(1-2):185-204, 1998. Google Scholar
  17. A. Krokhin and J. Opršal. The complexity of 3-colouring H-colourable graphs. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 1227-1239, 2019. URL: https://doi.org/10.1109/FOCS.2019.00076.
  18. Lászlo Lovász. Kneser’s conjecture, chromatic number, and homotopy. J. Combin. Theory Ser. A, 25(3):319-324, 1978. URL: https://doi.org/10.1016/0097-3165(78)90022-5.
  19. Thomas J. Schaefer. The complexity of satisfiability problems. In Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, STOC '78, pages 216-226, New York, NY, USA, 1978. ACM. URL: https://doi.org/10.1145/800133.804350.
  20. Marcin Wrochna. personal communication. Google Scholar
  21. Dmitriy Zhuk. A proof of the CSP dichotomy conjecture. J. ACM, 67(5), August 2020. URL: https://doi.org/10.1145/3402029.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact