Document Open Access Logo

Optimal Polynomial-Time Compression for Boolean Max CSP

Authors Bart M. P. Jansen , Michał Włodarczyk

PDF
Thumbnail PDF

File

LIPIcs.ESA.2020.63.pdf
  • Filesize: 0.81 MB
  • 19 pages

Document Identifiers

Author Details

Bart M. P. Jansen
  • Eindhoven University of Technology, The Netherlands
Michał Włodarczyk
  • Eindhoven University of Technology, The Netherlands

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 803421, ReduceSearch).
  • Włodarczyk, Michał: {The author was supported by the Foundation for Polish Science (FNP).}

Cite AsGet BibTex

Bart M. P. Jansen and Michał Włodarczyk. Optimal Polynomial-Time Compression for Boolean Max CSP. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 63:1-63:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ESA.2020.63

Abstract

In the Boolean maximum constraint satisfaction problem - Max CSP(Γ) - one is given a collection of weighted applications of constraints from a finite constraint language Γ, over a common set of variables, and the goal is to assign Boolean values to the variables so that the total weight of satisfied constraints is maximized. There exists a concise dichotomy theorem providing a criterion on Γ for the problem to be polynomial-time solvable and stating that otherwise it becomes NP-hard. We study the NP-hard cases through the lens of kernelization and provide a complete characterization of Max CSP(Γ) with respect to the optimal compression size. Namely, we prove that Max CSP(Γ) parameterized by the number of variables n is either polynomial-time solvable, or there exists an integer d ≥ 2 depending on Γ, such that: 1) An instance of Max CSP(Γ) can be compressed into an equivalent instance with 𝒪(n^d log n) bits in polynomial time, 2) Max CSP(Γ) does not admit such a compression to 𝒪(n^{d-ε}) bits unless NP ⊆ co-NP / poly. Our reductions are based on interpreting constraints as multilinear polynomials combined with the framework of constraint implementations. As another application of our reductions, we reveal tight connections between optimal running times for solving Max CSP(Γ). More precisely, we show that obtaining a running time of the form 𝒪(2^{(1-ε)n}) for particular classes of Max CSPs is as hard as breaching this barrier for Max d-SAT for some d.

Subject Classification

ACM Subject Classification
  • Theory of computation → Fixed parameter tractability
Keywords
  • constraint satisfaction problem
  • kernelization
  • exponential time algorithms

Metrics

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

Related Versions

References

  1. Josh Alman and Virginia Vassilevska Williams. OV Graphs Are (Probably) Hard Instances. In Thomas Vidick, editor, Proceedings of the 11th Innovations in Theoretical Computer Science Conference, ITCS 2020, volume 151 of Leibniz International Proceedings in Informatics (LIPIcs), pages 83:1-83:18, Dagstuhl, Germany, 2020. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.ITCS.2020.83.
  2. Noga Alon, Gregory Gutin, Eun Jung Kim, Stefan Szeider, and Anders Yeo. Solving MAX-r-SAT above a tight lower bound. Algorithmica, 61(3):638-655, 2011. Google Scholar
  3. David A. Mix Barrington, Richard Beigel, and Steven Rudich. Representing Boolean functions as polynomials modulo composite numbers. Computational Complexity, 4(4):367-382, 1994. URL: https://doi.org/10.1007/BF01263424.
  4. Richard Beigel. The polynomial method in circuit complexity. In Proceedings of the Eighth Annual Structure in Complexity Theory Conference, pages 82-95. IEEE Computer Society, 1993. URL: https://doi.org/10.1109/SCT.1993.336538.
  5. Karl Bringmann, Nick Fischer, and Marvin Künnemann. A Fine-Grained Analogue of Schaefer’s Theorem in P: Dichotomy of Exists^k-Forall-Quantified First-Order Graph Properties. In Amir Shpilka, editor, Proceedings of the 34th Computational Complexity Conference, CCC 2019, volume 137 of Leibniz International Proceedings in Informatics (LIPIcs), pages 31:1-31:27, Dagstuhl, Germany, 2019. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.CCC.2019.31.
  6. Andrei A. Bulatov. A dichotomy theorem for nonuniform CSPs. In Chris Umans, editor, Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, pages 319-330. IEEE Computer Society, 2017. URL: https://doi.org/10.1109/FOCS.2017.37.
  7. Andrei A. Bulatov, Martin Grohe, Phokion G. Kolaitis, and Andrei A. Krokhin, editors. The Constraint Satisfaction Problem: Complexity and Approximability, 25.10. - 30.10.2009, volume 09441 of Dagstuhl Seminar Proceedings. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Germany, 2009. URL: http://drops.dagstuhl.de/portals/09441/.
  8. Jin-Yi Cai and Xi Chen. Complexity of counting CSP with complex weights. J. ACM, 64(3):19:1-19:39, 2017. URL: https://doi.org/10.1145/2822891.
  9. Hubie Chen, Bart M. P. Jansen, and Astrid Pieterse. Best-case and worst-case sparsifiability of Boolean CSPs. Algorithmica, 2020. Online first. URL: https://doi.org/10.1007/s00453-019-00660-y.
  10. Nadia Creignou. A dichotomy theorem for maximum generalized satisfiability problems. J. Comput. Syst. Sci., 51(3):511-522, 1995. URL: https://doi.org/10.1006/jcss.1995.1087.
  11. Nadia Creignou, Sanjeev Khanna, and Madhu Sudan. Complexity classifications of Boolean constraint satisfaction problems, volume 7 of SIAM monographs on discrete mathematics and applications. SIAM, 2001. URL: https://doi.org/10.1137/1.9780898718546.
  12. Víctor Dalmau, Andrei A. Krokhin, and Rajsekar Manokaran. Towards a characterization of constant-factor approximable finite-valued CSPs. J. Comput. Syst. Sci., 97:14-27, 2018. URL: https://doi.org/10.1016/j.jcss.2018.03.003.
  13. Vladimir Deineko, Peter Jonsson, Mikael Klasson, and Andrei Krokhin. The approximability of MAX CSP with fixed-value constraints. J. ACM, 55(4), September 2008. URL: https://doi.org/10.1145/1391289.1391290.
  14. Holger Dell and Dieter van Melkebeek. Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. J. ACM, 61(4):23:1-23:27, 2014. URL: https://doi.org/10.1145/2629620.
  15. Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. Kernelization: Theory of Parameterized Preprocessing. Cambridge University Press, 2019. URL: https://doi.org/10.1017/9781107415157.
  16. Gregory Z. Gutin and Anders Yeo. Parameterized constraint satisfaction problems: a survey. In Andrei A. Krokhin and Stanislav Zivny, editors, The Constraint Satisfaction Problem: Complexity and Approximability, volume 7 of Dagstuhl Follow-Ups, pages 179-203. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. URL: https://doi.org/10.4230/DFU.Vol7.15301.7.
  17. Bart M. P. Jansen and Astrid Pieterse. Sparsification upper and lower bounds for graph problems and not-all-equal SAT. Algorithmica, 79(1):3-28, 2017. URL: https://doi.org/10.1007/s00453-016-0189-9.
  18. Bart M. P. Jansen and Astrid Pieterse. Optimal sparsification for some binary CSPs using low-degree polynomials. TOCT, 11(4):28:1-28:26, 2019. URL: https://doi.org/10.1145/3349618.
  19. Bart M. P. Jansen and Michal Wlodarczyk. Optimal polynomial-time compression for Boolean Max CSP. CoRR, abs/2002.03443, 2020. URL: http://arxiv.org/abs/2002.03443.
  20. Peter Jonsson and Andrei A. Krokhin. Maximum H-colourable subdigraphs and constraint optimization with arbitrary weights. J. Comput. Syst. Sci., 73(5):691-702, 2007. URL: https://doi.org/10.1016/j.jcss.2007.02.001.
  21. Sanjeev Khanna, Madhu Sudan, Luca Trevisan, and David P. Williamson. The approximability of constraint satisfaction problems. SIAM J. Comput., 30(6):1863-1920, 2000. URL: https://doi.org/10.1137/S0097539799349948.
  22. Stefan Kratsch, Dániel Marx, and Magnus Wahlström. Parameterized Complexity and Kernelizability of Max Ones and Exact Ones Problems. TOCT, 8(1):1:1-1:28, 2016. URL: https://doi.org/10.1145/2858787.
  23. Stefan Kratsch and Magnus Wahlström. Preprocessing of Min Ones problems: A dichotomy. In Samson Abramsky, Cyril Gavoille, Claude Kirchner, Friedhelm Meyer auf der Heide, and Paul G. Spirakis, editors, Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP 2010, volume 6198 of Lecture Notes in Computer Science, pages 653-665. Springer, 2010. URL: https://doi.org/10.1007/978-3-642-14165-2_55.
  24. Andrei A. Krokhin and Stanislav Zivny, editors. The Constraint Satisfaction Problem: Complexity and Approximability, volume 7 of Dagstuhl Follow-Ups. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. URL: http://www.dagstuhl.de/dagpub/978-3-95977-003-3.
  25. Victor Lagerkvist and Magnus Wahlström. Kernelization of constraint satisfaction problems: A study through universal algebra. In J. Christopher Beck, editor, Proceedings of the 23rd International Conference on Principles and Practice of Constraint Programming, CP 2017, volume 10416 of Lecture Notes in Computer Science, pages 157-171. Springer, 2017. URL: https://doi.org/10.1007/978-3-319-66158-2_11.
  26. Andrea Lincoln, Virginia Vassilevska Williams, and Ryan Williams. Tight hardness for shortest cycles and paths in sparse graphs. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, SODA ’18, pages 1236-1252, USA, 2018. Society for Industrial and Applied Mathematics. URL: https://doi.org/10.1137/1.9781611975031.80.
  27. Konstantin Makarychev and Yury Makarychev. Approximation Algorithms for CSPs. In Andrei Krokhin and Stanislav Zivny, editors, The Constraint Satisfaction Problem: Complexity and Approximability, volume 7 of Dagstuhl Follow-Ups, pages 287-325. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2017. URL: https://doi.org/10.4230/DFU.Vol7.15301.287.
  28. M. Minsky and S. Papert. Perceptrons. MIT Press, Cambridge, MA, 1969. Google Scholar
  29. Noam Nisan and Mario Szegedy. On the degree of Boolean functions as real polynomials. Computational Complexity, 4:301-313, 1994. URL: https://doi.org/10.1007/BF01263419.
  30. Hans Ulrich Simon. A tight Ω(log log n)-bound on the time for parallel RAM’s to compute nondegenerated boolean functions. Information and Control, 55(1-3):102-106, 1982. URL: https://doi.org/10.1016/S0019-9958(82)90477-6.
  31. Gábor Tardos and David A. Mix Barrington. A lower bound on the mod 6 degree of the OR function. Computational Complexity, 7(2):99-108, 1998. URL: https://doi.org/10.1007/PL00001597.
  32. Joachim von Zur Gathen and James R. Roche. Polynomials with two values. Combinatorica, 17(3):345-362, September 1997. URL: https://doi.org/10.1007/BF01215917.
  33. R. Ryan Williams. Algorithms and Resource Requirements for Fundamental Problems. PhD thesis, Carnegie Mellon University, USA, 2007. AAI3274191. Google Scholar
  34. Chee-Keng Yap. Some consequences of non-uniform conditions on uniform classes. Theor. Comput. Sci., 26:287-300, 1983. URL: https://doi.org/10.1016/0304-3975(83)90020-8.
  35. Dmitriy Zhuk. A proof of CSP dichotomy conjecture. In Chris Umans, editor, Proceeings of the 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, pages 331-342. IEEE Computer Society, 2017. URL: https://doi.org/10.1109/FOCS.2017.38.
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