Document Open Access Logo

Optimal Bounds for Dominating Set in Graph Streams

Authors Sanjeev Khanna, Christian Konrad

PDF

File

Thumbnail PDF
PDF
LIPIcs.ITCS.2022.93.pdf
  • Filesize: 0.88 MB
  • 23 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Streaming models
  • Theory of computation → Lower bounds and information complexity
  • Theory of computation → Graph algorithms analysis
Keywords
  • Streaming algorithms
  • communication complexity
  • information complexity
  • dominating set

Metrics

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

Abstract

We resolve the space complexity of one-pass streaming algorithms for Minimum Dominating Set (MDS) in both insertion-only and insertion-deletion streams (up to poly-logarithmic factors) where an input graph is revealed by a sequence of edge updates. Recently, streaming algorithms for the related Set Cover problem have received significant attention. Even though MDS can be viewed as a special case of Set Cover, it is however harder to solve in the streaming setting since the input stream consists of individual edges rather than entire vertex-neighborhoods, as is the case in Set Cover.
We prove the following results (n is the number of vertices of the input graph):  
1) In insertion-only streams, we give a one-pass semi-streaming algorithm (meaning Õ(n) space) with approximation factor Õ(√n). We also prove that every one-pass streaming algorithm with space o(n) has an approximation factor of Ω(n/log n).
Combined with a result by [Assadi et al., STOC'16] for Set Cover which, translated to MDS, shows that space Θ̃(n² / α) is necessary and sufficient for computing an α-approximation for every α = o(√n), this completely settles the space requirements for MDS in the insertion-only setting.
2) In insertion-deletion streams, we prove that space Ω(n² / (α log n)) is necessary for every approximation factor α ≤ Θ(n / log³ n). Combined with the Set Cover algorithm of [Assadi et al., STOC'16], which can be adapted to MDS even in the insertion-deletion setting to give an α-approximation in Õ(n² / α) space, this completely settles the space requirements for MDS in the insertion-deletion setting.

Cite As Get BibTex

Sanjeev Khanna and Christian Konrad. Optimal Bounds for Dominating Set in Graph Streams. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 93:1-93:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ITCS.2022.93

Author Details

Sanjeev Khanna
  • Department of Computer and Information Science, University of Pennsylvania, Philadelphia, PA, US
Christian Konrad
  • Department of Computer Science, University of Bristol, UK

Funding

  • Khanna, Sanjeev: Supported in part by NSF awards CCF-1910534, CCF-1926872, and CCF-2045128.
  • Konrad, Christian: Supported by EPSRC New Investigator Award EP/V010611/1.

References

  1. Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. Analyzing graph structure via linear measurements. In Yuval Rabani, editor, Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012, pages 459-467. SIAM, 2012. URL: https://doi.org/10.1137/1.9781611973099.40.
  2. Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. Spectral sparsification in dynamic graph streams. In Prasad Raghavendra, Sofya Raskhodnikova, Klaus Jansen, and José D. P. Rolim, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 16th International Workshop, APPROX 2013, and 17th International Workshop, RANDOM 2013, Berkeley, CA, USA, August 21-23, 2013. Proceedings, volume 8096 of Lecture Notes in Computer Science, pages 1-10. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-40328-6_1.
  3. Sepehr Assadi. Tight space-approximation tradeoff for the multi-pass streaming set cover problem. In Emanuel Sallinger, Jan Van den Bussche, and Floris Geerts, editors, Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2017, Chicago, IL, USA, May 14-19, 2017, pages 321-335. ACM, 2017. URL: https://doi.org/10.1145/3034786.3056116.
  4. Sepehr Assadi, Yu Chen, and Sanjeev Khanna. Polynomial pass lower bounds for graph streaming algorithms. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, pages 265-276, New York, NY, USA, 2019. Association for Computing Machinery. URL: https://doi.org/10.1145/3313276.3316361.
  5. Sepehr Assadi, Sanjeev Khanna, and Yang Li. Tight bounds for single-pass streaming complexity of the set cover problem. In Daniel Wichs and Yishay Mansour, editors, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 698-711. ACM, 2016. URL: https://doi.org/10.1145/2897518.2897576.
  6. Sepehr Assadi, Sanjeev Khanna, Yang Li, and Grigory Yaroslavtsev. Maximum matchings in dynamic graph streams and the simultaneous communication model. In Robert Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 1345-1364. SIAM, 2016. URL: https://doi.org/10.1137/1.9781611974331.ch93.
  7. Michael Barlow, Christian Konrad, and Charana Nandasena. Streaming set cover in practice. In Martin Farach-Colton and Sabine Storandt, editors, Proceedings of the Symposium on Algorithm Engineering and Experiments, ALENEX 2021, Virtual Conference, January 10-11, 2021, pages 181-192. SIAM, 2021. URL: https://doi.org/10.1137/1.9781611976472.14.
  8. Mark Braverman. Interactive information complexity. SIAM Rev., 59(4):803-846, 2017. URL: https://doi.org/10.1137/17M1139254.
  9. Amit Chakrabarti and Anthony Wirth. Incidence geometries and the pass complexity of semi-streaming set cover. In Robert Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 1365-1373. SIAM, 2016. URL: https://doi.org/10.1137/1.9781611974331.ch94.
  10. Graham Cormode, Howard J. Karloff, and Anthony Wirth. Set cover algorithms for very large datasets. In Jimmy Huang, Nick Koudas, Gareth J. F. Jones, Xindong Wu, Kevyn Collins-Thompson, and Aijun An, editors, Proceedings of the 19th ACM Conference on Information and Knowledge Management, CIKM 2010, Toronto, Ontario, Canada, October 26-30, 2010, pages 479-488. ACM, 2010. URL: https://doi.org/10.1145/1871437.1871501.
  11. Thomas M. Cover and Joy A. Thomas. Elements of information theory (2. ed.). Wiley, 2006. URL: http://www.elementsofinformationtheory.com/.
  12. Jacques Dark and Christian Konrad. Optimal lower bounds for matching and vertex cover in dynamic graph streams. In Shubhangi Saraf, editor, 35th Computational Complexity Conference, CCC 2020, July 28-31, 2020, Saarbrücken, Germany (Virtual Conference), volume 169 of LIPIcs, pages 30:1-30:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.CCC.2020.30.
  13. Erik D. Demaine, Piotr Indyk, Sepideh Mahabadi, and Ali Vakilian. On streaming and communication complexity of the set cover problem. In Fabian Kuhn, editor, Distributed Computing - 28th International Symposium, DISC 2014, Austin, TX, USA, October 12-15, 2014. Proceedings, volume 8784 of Lecture Notes in Computer Science, pages 484-498. Springer, 2014. URL: https://doi.org/10.1007/978-3-662-45174-8_33.
  14. Yuval Emek and Adi Rosén. Semi-streaming set cover. ACM Trans. Algorithms, 13(1):6:1-6:22, 2016. URL: https://doi.org/10.1145/2957322.
  15. 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.
  16. Sariel Har-Peled, Piotr Indyk, Sepideh Mahabadi, and Ali Vakilian. Towards tight bounds for the streaming set cover problem. In Tova Milo and Wang-Chiew Tan, editors, Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2016, San Francisco, CA, USA, June 26 - July 01, 2016, pages 371-383. ACM, 2016. URL: https://doi.org/10.1145/2902251.2902287.
  17. Monika Rauch Henzinger, Prabhakar Raghavan, and Sridhar Rajagopalan. Computing on data streams. In James M. Abello and Jeffrey Scott Vitter, editors, External Memory Algorithms, Proceedings of a DIMACS Workshop, New Brunswick, New Jersey, USA, May 20-22, 1998, volume 50 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 107-118. DIMACS/AMS, 1998. URL: https://doi.org/10.1090/dimacs/050/05.
  18. Piotr Indyk, Sepideh Mahabadi, Ronitt Rubinfeld, Jonathan R. Ullman, Ali Vakilian, and Anak Yodpinyanee. Fractional set cover in the streaming model. In Klaus Jansen, José D. P. Rolim, David Williamson, and Santosh S. Vempala, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2017, August 16-18, 2017, Berkeley, CA, USA, volume 81 of LIPIcs, pages 12:1-12:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.12.
  19. Hossein Jowhari, Mert Saglam, and Gábor Tardos. Tight bounds for lp samplers, finding duplicates in streams, and related problems. In Maurizio Lenzerini and Thomas Schwentick, editors, Proceedings of the 30th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2011, June 12-16, 2011, Athens, Greece, pages 49-58. ACM, 2011. URL: https://doi.org/10.1145/1989284.1989289.
  20. Michael Kapralov, Yin Tat Lee, Cameron Musco, Christopher Musco, and Aaron Sidford. Single pass spectral sparsification in dynamic streams. SIAM J. Comput., 46(1):456-477, 2017. URL: https://doi.org/10.1137/141002281.
  21. Michael Kapralov, Aida Mousavifar, Cameron Musco, Christopher Musco, Navid Nouri, Aaron Sidford, and Jakab Tardos. Fast and space efficient spectral sparsification in dynamic streams. In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 1814-1833. SIAM, 2020. URL: https://doi.org/10.1137/1.9781611975994.111.
  22. Christian Konrad. Maximum matching in turnstile streams. In Nikhil Bansal and Irene Finocchi, editors, Algorithms - ESA 2015 - 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings, volume 9294 of Lecture Notes in Computer Science, pages 840-852. Springer, 2015. URL: https://doi.org/10.1007/978-3-662-48350-3_70.
  23. Eyal Kushilevitz and Noam Nisan. Communication complexity. Cambridge University Press, 1997. Google Scholar
  24. Anup Rao and Amir Yehudayoff. Communication Complexity: and Applications. Cambridge University Press, 2020. URL: https://doi.org/10.1017/9781108671644.
  25. Tim Roughgarden. Communication complexity (for algorithm designers). Foundations and Trends® in Theoretical Computer Science, 11(3–4):217-404, 2016. URL: https://doi.org/10.1561/0400000076.
  26. Barna Saha and Lise Getoor. On maximum coverage in the streaming model & application to multi-topic blog-watch. In Proceedings of the SIAM International Conference on Data Mining, SDM 2009, April 30 - May 2, 2009, Sparks, Nevada, USA, pages 697-708. SIAM, 2009. URL: https://doi.org/10.1137/1.9781611972795.60.
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact