Document Open Access Logo

Beyond PCSP(1-in-3, NAE)

Authors Alex Brandts, Stanislav Živný

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2021.121.pdf
  • Filesize: 0.81 MB
  • 14 pages

Document Identifiers

Author Details

Alex Brandts
  • Department of Computer Science, University of Oxford, UK
Stanislav Živný
  • Department of Computer Science, University of Oxford, UK

Funding

This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 714532).
  • Brandts, Alex: Royal Society Enhancement Award and NSERC PGS Doctoral Award.
  • Živný, Stanislav: Royal Society University Research Fellowship.

Cite As Get BibTex

Alex Brandts and Stanislav Živný. Beyond PCSP(1-in-3, NAE). In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 121:1-121:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ICALP.2021.121

Abstract

The promise constraint satisfaction problem (PCSP) is a recently introduced vast generalisation of the constraint satisfaction problem (CSP) that captures approximability of satisfiable instances. A PCSP instance comes with two forms of each constraint: a strict one and a weak one. Given the promise that a solution exists using the strict constraints, the task is to find a solution using the weak constraints. While there are by now several dichotomy results for fragments of PCSPs, they all consider (in some way) symmetric PCSPs.
1-in-3-SAT and Not-All-Equal-3-SAT are classic examples of Boolean symmetric (non-promise) CSPs. While both problems are NP-hard, Brakensiek and Guruswami showed [SODA'18] that given a satisfiable instance of 1-in-3-SAT one can find a solution to the corresponding instance of (weaker) Not-All-Equal-3-SAT. In other words, the PCSP template (𝟏-in-𝟑,NAE) is tractable. 
We focus on non-symmetric PCSPs. In particular, we study PCSP templates obtained from the Boolean template (𝐭-in-𝐤, NAE) by either adding tuples to 𝐭-in-𝐤 or removing tuples from NAE. For the former, we classify all templates as either tractable or not solvable by the currently strongest known algorithm for PCSPs, the combined basic LP and affine IP relaxation of Brakensiek and Guruswami [SODA'20]. For the latter, we classify all templates as either tractable or NP-hard.

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
  • Theory of computation → Constraint and logic programming
Keywords
  • promise constraint satisfaction
  • PCSP
  • polymorphisms
  • algebraic approach

Metrics

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

Related Versions

References

  1. Per Austrin, Amey Bhangale, and Aditya Potukuchi. Improved inapproximability of rainbow coloring. In Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'20), pages 1479-1495, 2020. URL: https://doi.org/10.1137/1.9781611975994.90.
  2. 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.
  3. Libor Barto. Promises Make Finite (Constraint Satisfaction) Problems Infinitary. In Proceedings of the 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS'19), pages 1-8. IEEE, 2019. URL: https://doi.org/10.1109/LICS.2019.8785671.
  4. Libor Barto, Diego Battistelli, and Kevin M. Berg. Symmetric Promise Constraint Satisfaction Problems: Beyond the Boolean Case. In Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science (STACS'21), volume 187 of LIPIcs, pages 10:1-10:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.STACS.2021.10.
  5. Libor Barto, Jakub Bulín, Andrei A. Krokhin, and Jakub Opršal. Algebraic approach to promise constraint satisfaction. J. ACM, 2018. URL: http://arxiv.org/abs/1811.00970.
  6. Libor Barto, Andrei Krokhin, and Ross Willard. Polymorphisms, and how to use them. In Andrei Krokhin and Stanislav Zivny, editors, The Constraint Satisfaction Problem: Complexity and Approximability, volume 7 of Dagstuhl Follow-Ups, pages 1-44. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2017. URL: https://doi.org/10.4230/DFU.Vol7.15301.1.
  7. 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.
  8. Joshua Brakensiek and Venkatesan Guruswami. New hardness results for graph and hypergraph colorings. In Ran Raz, editor, 31st Conference on Computational Complexity (CCC 2016), volume 50 of Leibniz International Proceedings in Informatics (LIPIcs), pages 14:1-14:27, Dagstuhl, Germany, 2016. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.CCC.2016.14.
  9. Joshua Brakensiek and Venkatesan Guruswami. Promise Constraint Satisfaction: Structure Theory and a Symmetric Boolean Dichotomy. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'18), pages 1782-1801. SIAM, 2018. URL: https://doi.org/10.1137/1.9781611975031.117.
  10. Joshua Brakensiek and Venkatesan Guruswami. An Algorithmic Blend of LPs and Ring Equations for Promise CSPs. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'19), pages 436-455. SIAM, 2019. URL: https://doi.org/10.1137/1.9781611975482.28.
  11. Joshua Brakensiek and Venkatesan Guruswami. Symmetric polymorphisms and efficient decidability of promise CSPs. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 297-304, 2020. URL: https://doi.org/10.1137/1.9781611975994.18.
  12. Joshua Brakensiek, Venkatesan Guruswami, Marcin Wrochna, and Stanislav Živný. The power of the combined basic LP and affine relaxation for promise CSPs. SIAM Journal on Computing, 49:1232-1248, 2020. URL: https://doi.org/10.1137/20M1312745.
  13. Alex Brandts, Marcin Wrochna, and Stanislav Živný. The Complexity of Promise SAT on Non-Boolean Domains. In Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP'20), volume 168, pages 17:1-17:13. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.ICALP.2020.17.
  14. Alex Brandts and Stanislav Živný. Beyond PCSP(1-in-3,NAE), 2021. URL: http://arxiv.org/abs/2104.12800.
  15. Andrei Bulatov, Peter Jeavons, and Andrei Krokhin. Classifying the complexity of constraints using finite algebras. SIAM Journal on Computing, 34(3):720-742, 2005. URL: https://doi.org/10.1137/S0097539700376676.
  16. Andrei A. Bulatov. A dichotomy theorem for nonuniform CSPs. In Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 319-330, 2017. URL: https://doi.org/10.1109/FOCS.2017.37.
  17. 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.
  18. Irit Dinur, Elchanan Mossel, and Oded Regev. Conditional hardness for approximate coloring. SIAM J. Comput., 39(3):843-873, 2009. URL: https://doi.org/10.1137/07068062X.
  19. Irit Dinur, Oded Regev, and Clifford Smyth. The hardness of 3-uniform hypergraph coloring. Combinatorica, 25(5):519-535, 2005. URL: https://doi.org/10.1007/s00493-005-0032-4.
  20. Tomás Feder and Moshe Y. Vardi. The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory. SIAM Journal on Computing, 28(1):57-104, 1998. URL: https://doi.org/10.1137/S0097539794266766.
  21. Miron Ficak, Marcin Kozik, Miroslav Olšák, and Szymon Stankiewicz. Dichotomy for Symmetric Boolean PCSPs. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP'19), volume 132, pages 57:1-57:12. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.57.
  22. M. R. Garey and David S. Johnson. The complexity of near-optimal graph coloring. J. ACM, 23(1):43-49, 1976. URL: https://doi.org/10.1145/321921.321926.
  23. Venkatesan Guruswami and Sai Sandeep. d-To-1 Hardness of Coloring 3-Colorable Graphs with O(1) Colors. In Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP'20), volume 168 of LIPIcs, pages 62:1-62:12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.ICALP.2020.62.
  24. Pavol Hell and Jaroslav Nešetřil. On the Complexity of H-coloring. Journal of Combinatorial Theory, Series B, 48(1):92-110, 1990. URL: https://doi.org/10.1016/0095-8956(90)90132-J.
  25. Peter Jeavons, David A. Cohen, and Marc Gyssens. Closure properties of constraints. J. ACM, 44(4):527-548, 1997. URL: https://doi.org/10.1145/263867.263489.
  26. Richard M. Karp. Reducibility Among Combinatorial Problems. In Proceedings of a Symposium on the Complexity of Computer Computations, pages 85-103, 1972. URL: http://www.cs.berkeley.edu/%7Eluca/cs172/karp.pdf.
  27. Subhash Khot. On the power of unique 2-prover 1-round games. In Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC'02), pages 767-775. ACM, 2002. URL: https://doi.org/10.1145/509907.510017.
  28. Andrei Krokhin and Jakub Opršal. The complexity of 3-colouring H-colourable graphs. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS'19), pages 1227-1239, 2019. URL: https://doi.org/10.1109/FOCS.2019.00076.
  29. Thomas Schaefer. The complexity of satisfiability problems. In Proceedings of the tenth Annual ACM Symposium on the Theory of Computing (STOC '78), pages 216-226, 1978. URL: https://doi.org/10.1145/800133.804350.
  30. Marcin Wrochna and Stanislav Živný. Improved hardness for H-colourings of G-colourable graphs. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'20), pages 1426-1435, 2020. URL: https://doi.org/10.1137/1.9781611975994.86.
  31. Dmitriy Zhuk. A proof of the CSP dichotomy conjecture. J. ACM, 67(5):30:1-30:78, 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 About DROPS Imprint Privacy Contact