Parameterized Streaming Algorithms for Min-Ones d-SAT

Authors Akanksha Agrawal, Arindam Biswas, Édouard Bonnet, Nick Brettell, Radu Curticapean, Dániel Marx, Tillmann Miltzow, Venkatesh Raman, Saket Saurabh



PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2019.8.pdf
  • Filesize: 0.71 MB
  • 20 pages

Document Identifiers

Author Details

Akanksha Agrawal
  • Department of Computer Science, Ben-Gurion University of the Negev, Beer-Sheva, Israel
Arindam Biswas
  • The Institute of Mathematical Sciences, HBNI, Chennai, India
Édouard Bonnet
  • CNRS, ENS de Lyon, Université Claude Bernard Lyon 1, LIP UMR5668, France
Nick Brettell
  • Department of Computer Science, Durham University, Durham, UK
Radu Curticapean
  • BARC, University of Copenhagen, Copenhagen, Denmark
  • ITU Copenhagen, Copenhagen, Denmark
Dániel Marx
  • Institute for Computer Science and Control, MTA SZTAKI, Budapest, Hungary
Tillmann Miltzow
  • Department of Computer Science, Utrecht University, Utrecht, Netherlands
Venkatesh Raman
  • The Institute of Mathematical Sciences, HBNI, Chennai, India
Saket Saurabh
  • The Institute of Mathematical Sciences, HBNI, Chennai, India
  • Department of Computer Science, University of Bergen, Bergen, Norway

Cite AsGet BibTex

Akanksha Agrawal, Arindam Biswas, Édouard Bonnet, Nick Brettell, Radu Curticapean, Dániel Marx, Tillmann Miltzow, Venkatesh Raman, and Saket Saurabh. Parameterized Streaming Algorithms for Min-Ones d-SAT. In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 150, pp. 8:1-8:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.FSTTCS.2019.8

Abstract

In this work, we initiate the study of the Min-Ones d-SAT problem in the parameterized streaming model. An instance of the problem consists of a d-CNF formula F and an integer k, and the objective is to determine if F has a satisfying assignment which sets at most k variables to 1. In the parameterized streaming model, input is provided as a stream, just as in the usual streaming model. A key difference is that the bound on the read-write memory available to the algorithm is O(f(k) log n) (f: N -> N, a computable function) as opposed to the O(log n) bound of the usual streaming model. The other important difference is that the number of passes the algorithm makes over its input must be a (preferably small) function of k. We design a (k + 1)-pass parameterized streaming algorithm that solves Min-Ones d-SAT (d >= 2) using space O((kd^(ck) + k^d)log n) (c > 0, a constant) and a (d + 1)^k-pass algorithm that uses space O(k log n). We also design a streaming kernelization for Min-Ones 2-SAT that makes (k + 2) passes and uses space O(k^6 log n) to produce a kernel with O(k^6) clauses. To complement these positive results, we show that any k-pass algorithm for or Min-Ones d-SAT (d >= 2) requires space Omega(max{n^(1/k) / 2^k, log(n / k)}) on instances (F, k). This is achieved via a reduction from the streaming problem POT Pointer Chasing (Guha and McGregor [ICALP 2008]), which might be of independent interest. Given this, our (k + 1)-pass parameterized streaming algorithm is the best possible, inasmuch as the number of passes is concerned. In contrast to the results of Fafianie and Kratsch [MFCS 2014] and Chitnis et al. [SODA 2015], who independently showed that there are 1-pass parameterized streaming algorithms for Vertex Cover (a restriction of Min-Ones 2-SAT), we show using lower bounds from Communication Complexity that for any d >= 1, a 1-pass streaming algorithm for Min-Ones d-SAT requires space Omega(n). This excludes the possibility of a 1-pass parameterized streaming algorithm for the problem. Additionally, we show that any p-pass algorithm for the problem requires space Omega(n/p).

Subject Classification

ACM Subject Classification
  • Theory of computation → Streaming models
  • Theory of computation → Fixed parameter tractability
  • Theory of computation → Streaming, sublinear and near linear time algorithms
  • Mathematics of computing → Combinatorial algorithms
Keywords
  • min
  • ones
  • sat
  • d-sat
  • parameterized
  • kernelization
  • streaming
  • space
  • efficient
  • algorithm
  • parameter

Metrics

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

References

  1. Faisal N. Abu-Khzam. Kernelization Algorithms for D-Hitting Set Problems. In Algorithms and Data Structures, pages 434-445. Springer Berlin Heidelberg, 2007. Google Scholar
  2. Noga Alon, Yossi Matias, and Mario Szegedy. The Space Complexity of Approximating the Frequency Moments. Journal of Computer and System Sciences, 58(1):137-147, February 1999. Google Scholar
  3. Sanjeev Arora and Boaz Barak. Computational complexity: a modern approach. Cambridge University Press, 2009. Google Scholar
  4. Bengt Aspvall, Michael F. Plass, and Robert Endre Tarjan. A Linear-Time Algorithm for Testing the Truth of Certain Quantified Boolean Formulas. Information Processing Letters, 8(3):121-123, 1979. Google Scholar
  5. Rajesh Chitnis, Graham Cormode, Mohammadtaghi Hajiaghayi, and Morteza Monemizadeh. Parameterized Streaming: Maximal Matching and Vertex Cover. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1234-1251, 2015. Google Scholar
  6. Stephen A. Cook. The Complexity of Theorem-proving Procedures. In Proceedings of the 3rd Annual ACM Symposium on Theory of Computing (STOC), pages 151-158, 1971. Google Scholar
  7. Marek Cygan, Fedor V Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized algorithms, volume 4. Springer, 2015. Google Scholar
  8. Rod G. Downey and Michael R. Fellows. Fundamentals of Parameterized complexity. Springer-Verlag, 2013. Google Scholar
  9. Dingzhu Du, Jun Gu, Panos M Pardalos, et al. Satisfiability problem: theory and applications: DIMACS Workshop, March 11-13, 1996, volume 35. American Mathematical Soc., 1997. Google Scholar
  10. Shimon Even, Alon Itai, and Adi Shamir. On the complexity of timetable and multicommodity flow problems. SIAM Journal on Computing, 5(4):691-703, 1976. Google Scholar
  11. Stefan Fafianie and Stefan Kratsch. Streaming Kernelization. In Mathematical Foundations of Computer Science (MFCS), pages 275-286, 2014. Google Scholar
  12. Philippe Flajolet and G Nigel Martin. Probabilistic counting. In Proceedings of the 24th Annual Symposium on Foundations of Computer Science (FOCS), pages 76-82, 1983. Google Scholar
  13. Jörg Flum and Martin Grohe. Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2006. Google Scholar
  14. Fedor V. Fomin and Petteri Kaski. Exact Exponential Algorithms. Commun. ACM, 56(3):80-88, March 2013. Google Scholar
  15. Lance Fortnow. The Status of the P Versus NP Problem. Commun. ACM, 52(9):78-86, September 2009. Google Scholar
  16. Weiwei Gong and Xu Zhou. A survey of SAT solver. In AIP Conference Proceedings, volume 1836, 2017. Google Scholar
  17. Jun Gu, Paul W Purdom, John Franco, and Benjamin W Wah. Algorithms for the satisfiability (sat) problem. In Handbook of Combinatorial Optimization, pages 379-572. Springer, 1999. Google Scholar
  18. Sudipto Guha and Andrew McGregor. Tight Lower Bounds for Multi-Pass Stream Computation Via Pass Elimination. In International Colloquium on Automata, Languages and Programming (ICALP), volume 5125, pages 760-772, 2008. Google Scholar
  19. Dan Gusfield and Leonard Pitt. A Bounded Approximation for the Minimum Cost 2-Sat Problem. Algorithmica, 8(1-6):103-117, 1992. Google Scholar
  20. Monika Rauch Henzinger, Prabhakar Raghavan, and Sridhar Rajagopalan. Computing on data streams. In External Memory Algorithms, Proceedings of a DIMACS Workshop, pages 107-118, 1998. Google Scholar
  21. Dorit S Hochbaum, Nimrod Megiddo, Joseph (Seffi) Naor, and Arie Tamir. Tight Bounds and 2-Approximation Algorithms for Integer Programs with Two Variables per Inequality. Mathematical Programming, 62(1-3):69-83, 1993. Google Scholar
  22. David S Johnson. Approximation algorithms for combinatorial problems. Journal of computer and system sciences, 9(3):256-278, 1974. Google Scholar
  23. Richard M Karp. Reducibility among combinatorial problems. In Complexity of computer computations, pages 85-103. Springer, 1972. Google Scholar
  24. Stefan Kratsch and Magnus Wahlström. Two Edge Modification Problems without Polynomial Kernels. In Parameterized and Exact Computation, 4th International Workshop, (IWPEC), pages 264-275, 2009. Google Scholar
  25. Melven R Krom. The decision problem for a class of first-order formulas in which all disjunctions are binary. Mathematical Logic Quarterly, 13(1-2):15-20, 1967. Google Scholar
  26. Eyal Kushilevitz and Noam Nisan. Communication Complexity. Cambridge University Press, New York, NY, USA, 1997. Google Scholar
  27. Neeldhara Misra, N. S. Narayanaswamy, Venkatesh Raman, and Bal Sri Shankar. Solving Min Ones 2-Sat as Fast as Vertex Cover. Theoretical Computer Science, 506:115-121, 2013. Google Scholar
  28. J Ian Munro and Mike S Paterson. Selection and sorting with limited storage. In Proceedings of the 19th Annual Symposium on Foundations of Computer Science (FOCS), pages 253-258, 1978. Google Scholar
  29. Rolf Niedermeier. Invitation to fixed-parameter algorithms. Oxford Lecture Series in Mathematics and Its Applications. Oxford University Press, 2006. Google Scholar
  30. Thomas Stützle, Holger Hoos, and Andrea Roli. A review of the literature on local search algorithms for MAX-SAT. Rapport technique AIDA-01-02, Intellectics Group, Darmstadt University of Technology, Germany, 2001. Google Scholar
  31. Stefan Szeider. On fixed-parameter tractable parameterizations of SAT. In International Conference on Theory and Applications of Satisfiability Testing, pages 188-202. Springer, 2003. Google Scholar
  32. Gerhard J Woeginger. Exact algorithms for NP-hard problems: A survey. In Combinatorial Optimization—Eureka, You Shrink!, pages 185-207. Springer, 2003. Google Scholar
  33. Mihalis Yannakakis. Node- and Edge-Deletion NP-Complete Problems. In Proceedings of the 10th Annual ACM Symposium on Theory of Computing (STOC), pages 253-264, 1978. Google Scholar
  34. Mihalis Yannakakis. On the approximation of maximum satisfiability. Journal of Algorithms, 17(3):475-502, 1994. Google Scholar
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