Document Open Access Logo

Optimal Sparsification for Some Binary CSPs Using Low-Degree Polynomials

Authors Bart M. P. Jansen, Astrid Pieterse

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2016.71.pdf
  • Filesize: 0.57 MB
  • 14 pages

Document Identifiers

Author Details

Bart M. P. Jansen
Astrid Pieterse

Cite AsGet BibTex

Bart M. P. Jansen and Astrid Pieterse. Optimal Sparsification for Some Binary CSPs Using Low-Degree Polynomials. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 71:1-71:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.MFCS.2016.71

Abstract

This paper analyzes to what extent it is possible to efficiently reduce the number of clauses in NP-hard satisfiability problems, without changing the answer. Upper and lower bounds are established using the concept of kernelization. Existing results show that if NP is not contained in coNP/poly, no efficient preprocessing algorithm can reduce n-variable instances of CNF-SAT with d literals per clause, to equivalent instances with O(n^{d-epsilon}) bits for any epsilon > 0. For the Not-All-Equal SAT problem, a compression to size tilde-O(n^{d-1}) exists. We put these results in a common framework by analyzing the compressibility of binary CSPs. We characterize constraint types based on the minimum degree of multivariate polynomials whose roots correspond to the satisfying assignments, obtaining (nearly) matching upper and lower bounds in several settings. Our lower bounds show that not just the number of constraints, but also the encoding size of individual constraints plays an important role. For example, for Exact Satisfiability with unbounded clause length it is possible to efficiently reduce the number of constraints to n+1, yet no polynomial-time algorithm can reduce to an equivalent instance with O(n^{2-epsilon}) bits for any epsilon > 0, unless NP is contained in coNP/poly.
Keywords
  • constraint satisfaction problem
  • sparsification
  • satisfiability
  • kernelization

Metrics

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

References

  1. David A. Mix Barrington. Some problems involving Razborov-Smolensky polynomials. In Proceedings of the London Mathematical Society Symposium on Boolean Function Complexity, pages 109-128. Cambridge University Press, 1992. URL: http://dx.doi.org/10.1017/CBO9780511526633.010.
  2. 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: http://dx.doi.org/10.1007/BF01263424.
  3. Abhishek Bhowmick and Shachar Lovett. Nonclassical Polynomials as a Barrier to Polynomial Lower Bounds. In Proc. 30th CCC, volume 33 of LIPIcs, pages 72-87, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.CCC.2015.72.
  4. Hans L. Bodlaender. Kernelization, exponential lower bounds. In Encyclopedia of Algorithms. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-642-27848-8_521-1.
  5. Hans L. Bodlaender, Bart M. P. Jansen, and Stefan Kratsch. Kernelization lower bounds by cross-composition. SIAM J. Discrete Math., 28(1):277-305, 2014. URL: http://dx.doi.org/10.1137/120880240.
  6. Hans L. Bodlaender, Stéphan Thomassé, and Anders Yeo. Kernel bounds for disjoint cycles and disjoint paths. Theor. Comput. Sci., 412(35):4570-4578, 2011. URL: http://dx.doi.org/10.1016/j.tcs.2011.04.039.
  7. Andrei A. Bulatov and Dániel Marx. Constraint satisfaction parameterized by solution size. SIAM J. Comput., 43(2):573-616, 2014. URL: http://dx.doi.org/10.1137/120882160.
  8. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-21275-3.
  9. Holger Dell, Eun Jung Kim, Michael Lampis, Valia Mitsou, and Tobias Mömke. Complexity and approximability of parameterized MAX-CSPs. In Proc. 10th IPEC, volume 43 of LIPIcs, pages 294-306, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.IPEC.2015.294.
  10. 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: http://dx.doi.org/10.1145/2629620.
  11. Michael Dom, Daniel Lokshtanov, and Saket Saurabh. Kernelization lower bounds through colors and IDs. ACM Transactions on Algorithms, 11(2):13, 2014. URL: http://dx.doi.org/10.1145/2650261.
  12. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. Google Scholar
  13. J. Flum and M. Grohe. Parameterized Complexity Theory. Springer-Verlag, 2006. Google Scholar
  14. Lance Fortnow and Rahul Santhanam. Infeasibility of instance compression and succinct PCPs for NP. J. Comput. Syst. Sci., 77(1):91-106, 2011. URL: http://dx.doi.org/10.1016/j.jcss.2010.06.007.
  15. Ben Green and Terence Tao. The primes contain arbitrarily long arithmetic progressions. Annals of Mathematics, 167(2):481-547, 2008. URL: http://dx.doi.org/10.4007/annals.2008.167.481.
  16. Gregory Gutin. Kernelization: Constraint satisfaction problems parameterized above average. In Ming-Yang Kao, editor, Encyclopedia of Algorithms. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-642-27848-8_524-1.
  17. Leslie Hogben. Handbook of Linear Algebra, Second Edition. Chapman and Hall/CRC, 2014. Google Scholar
  18. Bart M. P. Jansen. On sparsification for computing treewidth. Algorithmica, 71(3):605-635, 2015. URL: http://dx.doi.org/10.1007/s00453-014-9924-2.
  19. Bart M. P. Jansen. Constrained bipartite vertex cover: The easy kernel is essentially tight. In Proc. 33rd STACS, volume 47 of LIPIcs, pages 45:1-45:13. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2016.45.
  20. Bart M. P. Jansen and Astrid Pieterse. Sparsification upper and lower bounds for graphs problems and not-all-equal SAT. In Proc. 10th IPEC, volume 43 of LIPIcs, pages 163-174, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.IPEC.2015.163.
  21. Bart M.P. Jansen and Astrid Pieterse. Optimal sparsification for some binary CSPs using low-degree polynomials. CoRR, abs/1606.03233v1, 2016. URL: http://arxiv.org/abs/1606.03233v1.
  22. R. M. Karp. Reducibility Among Combinatorial Problems. In Complexity of Computer Computations, pages 85-103. Plenum Press, 1972. Google Scholar
  23. Stefan Kratsch. Recent developments in kernelization: A survey. Bulletin of the EATCS, 113:58-97, 2014. Google Scholar
  24. Stefan Kratsch, Dániel Marx, and Magnus Wahlström. Parameterized complexity and kernelizability of max ones and exact ones problems. TOCT, 8(1):1, 2016. URL: http://dx.doi.org/10.1145/2858787.
  25. Stefan Kratsch and Magnus Wahlström. Preprocessing of min ones problems: A dichotomy. In Proc. 37th ICALP, volume 6198 of Lecture Notes in Computer Science, pages 653-665, 2010. URL: http://dx.doi.org/10.1007/978-3-642-14165-2_55.
  26. Daniel Lokshtanov, Neeldhara Misra, and Saket Saurabh. Kernelization - preprocessing with a guarantee. In The Multivariate Algorithmic Revolution and Beyond - Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday, volume 7370 of Lecture Notes in Computer Science, pages 129-161, 2012. URL: http://dx.doi.org/10.1007/978-3-642-30891-8_10.
  27. Lásló Lovász. Chromatic number of hypergraphs and linear algebra. In Studia Scientiarum Mathematicarum Hungarica 11, pages 113-114, 1976. Google Scholar
  28. Thomas J. Schaefer. The complexity of satisfiability problems. In Proc. 10th ACM Symposium on Theory of Computing, pages 216-226, 1978. URL: http://dx.doi.org/10.1145/800133.804350.
  29. 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: http://dx.doi.org/10.1007/PL00001597.
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