Document Open Access Logo

Towards a Theory of Parameterized Streaming Algorithms

Authors Rajesh Chitnis, Graham Cormode

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2019.7.pdf
  • Filesize: 0.65 MB
  • 15 pages

Document Identifiers

Author Details

Rajesh Chitnis
  • School of Computer Science, University of Birmingham, UK
Graham Cormode
  • University of Warwick, UK

Funding

  • Chitnis, Rajesh: Work done while at University of Warwick, UK and supported by ERC grant 2014-CoG 647557.
  • Cormode, Graham: Supported by ERC grant 2014-CoG 647557.

Acknowledgements

We thank MohammadTaghi Hajiaghayi, Robert Krauthgamer and Morteza Monemizadeh for helpful discussions. Algorithm 1 was suggested to us by Arnold Filtser.

Cite AsGet BibTex

Rajesh Chitnis and Graham Cormode. Towards a Theory of Parameterized Streaming Algorithms. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, pp. 7:1-7:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.IPEC.2019.7

Abstract

Parameterized complexity attempts to give a more fine-grained analysis of the complexity of problems: instead of measuring the running time as a function of only the input size, we analyze the running time with respect to additional parameters. This approach has proven to be highly successful in delineating our understanding of NP-hard problems. Given this success with the TIME resource, it seems but natural to use this approach for dealing with the SPACE resource. First attempts in this direction have considered a few individual problems, with some success: Fafianie and Kratsch [MFCS'14] and Chitnis et al. [SODA'15] introduced the notions of streaming kernels and parameterized streaming algorithms respectively. For example, the latter shows how to refine the Omega(n^2) bit lower bound for finding a minimum Vertex Cover (VC) in the streaming setting by designing an algorithm for the parameterized k-VC problem which uses O(k^{2}log n) bits. In this paper, we initiate a systematic study of graph problems from the paradigm of parameterized streaming algorithms. We first define a natural hierarchy of space complexity classes of FPS, SubPS, SemiPS, SupPS and BrutePS, and then obtain tight classifications for several well-studied graph problems such as Longest Path, Feedback Vertex Set, Dominating Set, Girth, Treewidth, etc. into this hierarchy (see Figure 1 and Table 1). On the algorithmic side, our parameterized streaming algorithms use techniques from the FPT world such as bidimensionality, iterative compression and bounded-depth search trees. On the hardness side, we obtain lower bounds for the parameterized streaming complexity of various problems via novel reductions from problems in communication complexity. We also show a general (unconditional) lower bound for space complexity of parameterized streaming algorithms for a large class of problems inspired by the recently developed frameworks for showing (conditional) kernelization lower bounds. Parameterized algorithms and streaming algorithms are approaches to cope with TIME and SPACE intractability respectively. It is our hope that this work on parameterized streaming algorithms leads to two-way flow of ideas between these two previously separated areas of theoretical computer science.

Subject Classification

ACM Subject Classification
  • Theory of computation → Streaming, sublinear and near linear time algorithms
Keywords
  • Parameterized Algorithms
  • Streaming Algorithms
  • Kernels

Metrics

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

Related Versions

References

  1. Amir Abboud, Keren Censor-Hillel, Seri Khoury, and Ami Paz. Smaller Cuts, Higher Lower Bounds. CoRR, abs/1901.01630, 2019. URL: http://arxiv.org/abs/1901.01630.
  2. Sepehr Assadi, Sanjeev Khanna, and Yang Li. Tight bounds for single-pass streaming complexity of the set cover problem. In STOC, pages 698-711, 2016. URL: https://doi.org/10.1145/2897518.2897576.
  3. Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, and Danny Hermelin. On Problems Without Polynomial Kernels. J. Comput. Syst. Sci., 75(8):423-434, 2009. URL: https://doi.org/10.1016/j.jcss.2009.04.001.
  4. Marc Bury, Elena Grigorescu, Andrew McGregor, Morteza Monemizadeh, Chris Schwiegelshohn, Sofya Vorotnikova, and Samson Zhou. Structural Results on Matching Estimation with Applications to Streaming. Algorithmica, 81(1):367-392, 2019. URL: https://doi.org/10.1007/s00453-018-0449-y.
  5. Jianer Chen, Fedor V. Fomin, Yang Liu, Songjian Lu, and Yngve Villanger. Improved algorithms for feedback vertex set problems. J. Comput. Syst. Sci., 74(7):1188-1198, 2008. URL: https://doi.org/10.1016/j.jcss.2008.05.002.
  6. Jianer Chen, Yang Liu, Songjian Lu, Barry O'Sullivan, and Igor Razgon. A fixed-parameter algorithm for the directed feedback vertex set problem. J. ACM, 55(5):21:1-21:19, 2008. URL: https://doi.org/10.1145/1411509.1411511.
  7. Rajesh Chitnis, Graham Cormode, Hossein Esfandiari, MohammadTaghi Hajiaghayi, Andrew McGregor, Morteza Monemizadeh, and Sofya Vorotnikova. Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams. In SODA, pages 1326-1344, 2016. URL: https://doi.org/10.1137/1.9781611974331.ch92.
  8. Rajesh Hemant Chitnis, Graham Cormode, Hossein Esfandiari, MohammadTaghi Hajiaghayi, and Morteza Monemizadeh. Brief Announcement: New Streaming Algorithms for Parameterized Maximal Matching & Beyond. In SPAA, pages 56-58, 2015. URL: https://doi.org/10.1145/2755573.2755618.
  9. Rajesh Hemant Chitnis, Graham Cormode, Mohammad Taghi Hajiaghayi, and Morteza Monemizadeh. Parameterized Streaming: Maximal Matching and Vertex Cover. In SODA, pages 1234-1251, 2015. URL: https://doi.org/10.1137/1.9781611973730.82.
  10. Rajesh Hemant Chitnis, Marek Cygan, Mohammad Taghi Hajiaghayi, and Dániel Marx. Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable. ACM Trans. Algorithms, 11(4):28:1-28:28, 2015. URL: https://doi.org/10.1145/2700209.
  11. Julia Chuzhoy and Zihan Tan. Towards Tight(er) Bounds for the Excluded Grid Theorem. In SODA, pages 1445-1464, 2019. URL: https://doi.org/10.1137/1.9781611975482.88.
  12. Graham Cormode, Hossein Jowhari, Morteza Monemizadeh, and S. Muthukrishnan. The Sparse Awakens: Streaming Algorithms for Matching Size Estimation in Sparse Graphs. In ESA, pages 29:1-29:15, 2017. URL: https://doi.org/10.4230/LIPIcs.ESA.2017.29.
  13. Michael S. Crouch, Andrew McGregor, and Daniel Stubbs. Dynamic Graphs in the Sliding-Window Model. In ESA, pages 337-348, 2013. URL: https://doi.org/10.1007/978-3-642-40450-4_29.
  14. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-21275-3.
  15. Frank K. H. A. Dehne, Michael R. Fellows, Frances A. Rosamond, and Peter Shaw. Greedy Localization, Iterative Compression, Modeled Crown Reductions: New FPT Techniques, an Improved Algorithm for Set Splitting, and a Novel 2k Kernelization for Vertex Cover. In IWPEC, pages 271-280, 2004. URL: https://doi.org/10.1007/978-3-540-28639-4_24.
  16. Holger Dell. AND-Compression of NP-Complete Problems: Streamlined Proof and Minor Observations. Algorithmica, 75(2):403-423, 2016. URL: https://doi.org/10.1007/s00453-015-0110-y.
  17. Holger Dell and Dieter van Melkebeek. Satisfiability Allows no Nontrivial Sparsification Unless the Polynomial-Time Hierarchy Collapses. In STOC, pages 251-260, 2010. URL: https://doi.org/10.1145/1806689.1806725.
  18. Erik D. Demaine, Fedor V. Fomin, Mohammad Taghi Hajiaghayi, and Dimitrios M. Thilikos. Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs. J. ACM, 52(6):866-893, 2005. URL: https://doi.org/10.1145/1101821.1101823.
  19. Erik D. Demaine and MohammadTaghi Hajiaghayi. The Bidimensionality Theory and Its Algorithmic Applications. Comput. J., 51(3):292-302, 2008. URL: https://doi.org/10.1093/comjnl/bxm033.
  20. Rodney G. Downey and Michael R. Fellows. Parameterized Complexity. Monographs in Computer Science. Springer, 1999. URL: https://doi.org/10.1007/978-1-4612-0515-9.
  21. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. URL: https://doi.org/10.1007/978-1-4471-5559-1.
  22. Andrew Drucker. New Limits to Classical and Quantum Instance Compression. In FOCS, pages 609-618, 2012. URL: https://doi.org/10.1109/FOCS.2012.71.
  23. David Eppstein, Zvi Galil, Giuseppe F. Italiano, and Amnon Nissenzweig. Sparsification - a technique for speeding up dynamic graph algorithms. J. ACM, 44(5):669-696, 1997. URL: https://doi.org/10.1145/265910.265914.
  24. Hossein Esfandiari, Mohammad Taghi Hajiaghayi, Vahid Liaghat, Morteza Monemizadeh, and Krzysztof Onak. Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond. In SODA, pages 1217-1233, 2015. URL: https://doi.org/10.1137/1.9781611973730.81.
  25. Stefan Fafianie and Stefan Kratsch. Streaming Kernelization. In MFCS, pages 275-286, 2014. URL: https://doi.org/10.1007/978-3-662-44465-8_24.
  26. Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang. On graph problems in a semi-streaming model. Theor. Comput. Sci., 348(2-3):207-216, 2005. URL: https://doi.org/10.1016/j.tcs.2005.09.013.
  27. Lance Fortnow and Rahul Santhanam. Infeasibility of Instance Compression and Succinct PCPs for NP. J. Comput. Syst. Sci., 77(1):91-106, 2011. URL: https://doi.org/10.1016/j.jcss.2010.06.007.
  28. Sariel Har-Peled, Piotr Indyk, Sepideh Mahabadi, and Ali Vakilian. Towards Tight Bounds for the Streaming Set Cover Problem. In PODS, pages 371-383, 2016. URL: https://doi.org/10.1145/2902251.2902287.
  29. Monika Rauch Henzinger, Prabhakar Raghavan, and Sridhar Rajagopalan. Computing on data streams. External memory algorithms, 50:107-118, 1998. Google Scholar
  30. Eyal Kushilevitz and Noam Nisan. Communication Complexity. Cambridge University Press, 1997. Google Scholar
  31. Andrew McGregor and Sofya Vorotnikova. Planar Matching in Streams Revisited. In APPROX/RANDOM, pages 17:1-17:12, 2016. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2016.17.
  32. Andrew McGregor and Sofya Vorotnikova. A Simple, Space-Efficient, Streaming Algorithm for Matchings in Low Arboricity Graphs. In SOSA, pages 14:1-14:4, 2018. URL: https://doi.org/10.4230/OASIcs.SOSA.2018.14.
  33. S. Muthukrishnan. Data Streams: Algorithms and Applications. Foundations and Trends in Theoretical Computer Science, 1(2), 2005. URL: https://doi.org/10.1561/0400000002.
  34. Bruce A. Reed, Kaleigh Smith, and Adrian Vetta. Finding odd cycle transversals. Oper. Res. Lett., 32(4):299-301, 2004. URL: https://doi.org/10.1016/j.orl.2003.10.009.
  35. Xiaoming Sun and David P. Woodruff. Tight Bounds for Graph Problems in Insertion Streams. In APPROX-RANDOM, pages 435-448, 2015. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.435.
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