Streaming Complexity of Spanning Tree Computation

Authors Yi-Jun Chang, Martín Farach-Colton, Tsan-Sheng Hsu, Meng-Tsung Tsai



PDF
Thumbnail PDF

File

LIPIcs.STACS.2020.34.pdf
  • Filesize: 0.54 MB
  • 19 pages

Document Identifiers

Author Details

Yi-Jun Chang
  • ETH Zürich, Switzerland
Martín Farach-Colton
  • Rutgers University, USA
Tsan-Sheng Hsu
  • Academia Sinica, Taipei City, Taiwan
Meng-Tsung Tsai
  • National Chiao Tung University, Hsinchu, Taiwan

Acknowledgements

We thank the anonymous reviewers for their helpful comments, and Eric Allender and Meng Li for their insightful discussions.

Cite AsGet BibTex

Yi-Jun Chang, Martín Farach-Colton, Tsan-Sheng Hsu, and Meng-Tsung Tsai. Streaming Complexity of Spanning Tree Computation. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 34:1-34:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.STACS.2020.34

Abstract

The semi-streaming model is a variant of the streaming model frequently used for the computation of graph problems. It allows the edges of an n-node input graph to be read sequentially in p passes using Õ(n) space. If the list of edges includes deletions, then the model is called the turnstile model; otherwise it is called the insertion-only model. In both models, some graph problems, such as spanning trees, k-connectivity, densest subgraph, degeneracy, cut-sparsifier, and (Δ+1)-coloring, can be exactly solved or (1+ε)-approximated in a single pass; while other graph problems, such as triangle detection and unweighted all-pairs shortest paths, are known to require Ω̃(n) passes to compute. For many fundamental graph problems, the tractability in these models is open. In this paper, we study the tractability of computing some standard spanning trees, including BFS, DFS, and maximum-leaf spanning trees. Our results, in both the insertion-only and the turnstile models, are as follows. - Maximum-Leaf Spanning Trees: This problem is known to be APX-complete with inapproximability constant ρ ∈ [245/244, 2). By constructing an ε-MLST sparsifier, we show that for every constant ε > 0, MLST can be approximated in a single pass to within a factor of 1+ε w.h.p. (albeit in super-polynomial time for ε ≤ ρ-1 assuming P ≠ NP) and can be approximated in polynomial time in a single pass to within a factor of ρ_n+ε w.h.p., where ρ_n is the supremum constant that MLST cannot be approximated to within using polynomial time and Õ(n) space. In the insertion-only model, these algorithms can be deterministic. - BFS Trees: It is known that BFS trees require ω(1) passes to compute, but the naïve approach needs O(n) passes. We devise a new randomized algorithm that reduces the pass complexity to O(√n), and it offers a smooth tradeoff between pass complexity and space usage. This gives a polynomial separation between single-source and all-pairs shortest paths for unweighted graphs. - DFS Trees: It is unknown whether DFS trees require more than one pass. The current best algorithm by Khan and Mehta [STACS 2019] takes Õ(h) passes, where h is the height of computed DFS trees. Note that h can be as large as Ω(m/n) for n-node m-edge graphs. Our contribution is twofold. First, we provide a simple alternative proof of this result, via a new connection to sparse certificates for k-node-connectivity. Second, we present a randomized algorithm that reduces the pass complexity to O(√n), and it also offers a smooth tradeoff between pass complexity and space usage.

Subject Classification

ACM Subject Classification
  • Theory of computation → Streaming, sublinear and near linear time algorithms
Keywords
  • Max-Leaf Spanning Trees
  • BFS Trees
  • DFS Trees

Metrics

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

References

  1. Farid M. Ablayev. Lower bounds for one-way probabilistic communication complexity and their application to space complexity. Theor. Comput. Sci., 157(2):139-159, 1996. Google Scholar
  2. Alok Aggarwal and Richard J. Anderson. A random NC algorithm for depth first search. Combinatorica, 8(1):1-12, March 1988. Google Scholar
  3. Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. Analyzing graph structure via linear measurements. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012, pages 459-467, 2012. Google Scholar
  4. Sepehr Assadi, Yu Chen, and Sanjeev Khanna. Sublinear algorithms for (Δ + 1) vertex coloring. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 767-786, 2019. Google Scholar
  5. Jesse Beisegel. Characterising AT-free graphs with BFS. In Graph-Theoretic Concepts in Computer Science - 44th International Workshop, WG 2018, Cottbus, Germany, June 27-29, 2018, Proceedings, pages 15-26, 2018. Google Scholar
  6. Richard Bellman. On a routing problem. Quarterly of Applied Mathematics, 16(1):87-90, 1958. Google Scholar
  7. Vladimir Braverman, Rafail Ostrovsky, and Dan Vilenchik. How hard is counting triangles in the streaming model? In Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I, pages 244-254, 2013. Google Scholar
  8. Joseph Cheriyan and Ramakrishna Thurimella. Algorithms for parallel k-vertex connectivity and sparse certificates. In Proceedings of the Twenty-third Annual ACM Symposium on Theory of Computing, STOC '91, pages 391-401. ACM, 1991. Google Scholar
  9. Miroslav Chlebík and Janka Chlebíková. Approximation hardness of dominating set problems in bounded degree graphs. Inf. Comput., 206(11):1264-1275, 2008. Google Scholar
  10. Derek G. Corneil, Feodor F. Dragan, and Ekkehard Köhler. On the power of BFS to determine a graph’s diameter. Networks, 42(4):209-222, 2003. Google Scholar
  11. M. Elkin. Distributed exact shortest paths in sublinear time. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 757-770, New York, NY, USA, 2017. ACM. Google Scholar
  12. David Eppstein, Zvi Galil, Giuseppe F. Italiano, and Amnon Nissenzweig. Sparsification - a technique for speeding up dynamic graph algorithms. JACM, 44(5):669-696, 1997. Google Scholar
  13. Shimon Even and Robert Endre Tarjan. Computing an st-numbering. Theoretical Computer Science, 2(3):339-344, 1976. Google Scholar
  14. Martin Farach-Colton, Tsan-sheng Hsu, Meng Li, and Meng-Tsung Tsai. Finding articulation points of large graphs in linear time. In Algorithms and Data Structures - 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015. Proceedings, pages 363-372, 2015. Google Scholar
  15. Martin Farach-Colton and Meng-Tsung Tsai. Tight approximations of degeneracy in large graphs. In LATIN 2016: Theoretical Informatics - 12th Latin American Symposium, Ensenada, Mexico, April 11-15, 2016, Proceedings, pages 429-440, 2016. Google Scholar
  16. 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. Google Scholar
  17. Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang. Graph distances in the data-stream model. SIAM J. Comput., 38(5):1709-1727, 2008. Google Scholar
  18. T. Fleiner and G. Wiener. Coloring signed graphs using DFS. Optimization Letters, 10(4):865-869, April 2016. Google Scholar
  19. L.R. Ford. Network Flow Theory. Paper P. Rand Corporation, 1956. Google Scholar
  20. Giulia Galbiati, Francesco Maffioli, and Angelo Morzenti. A short note on the approximability of the maximum leaves spanning tree problem. Inf. Process. Lett., 52(1):45-49, 1994. Google Scholar
  21. Rajiv Gandhi, Mohammad Taghi Hajiaghayi, Guy Kortsarz, Manish Purohit, and Kanthi K. Sarpatwar. On maximum leaf trees and connections to connected maximum cut problems. Inf. Process. Lett., 129:31-34, 2018. Google Scholar
  22. Mohsen. Ghaffari and Jason. Li. Improved distributed algorithms for exact shortest paths. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC), 2018. Google Scholar
  23. Mohsen Ghaffari and Merav Parter. Near-optimal distributed DFS in planar graphs. In 31st International Symposium on Distributed Computing, DISC 2017, October 16-20, 2017, Vienna, Austria, pages 21:1-21:16, 2017. Google Scholar
  24. A. V. Goldberg, S. A. Plotkin, and P. M. Vaidya. Sublinear-time parallel algorithms for matching and related problems. JALG, 14(2):180-213, 1993. Google Scholar
  25. Sudipto Guha, Andrew McGregor, and David Tench. Vertex and hyperedge connectivity in dynamic graph streams. In Proceedings of the 34th ACM Symposium on Principles of Database Systems, PODS 2015, Melbourne, Victoria, Australia, May 31 - June 4, 2015, pages 241-247, 2015. Google Scholar
  26. Mohammad Taghi Hajiaghayi, Guy Kortsarz, Robert MacDavid, Manish Purohit, and Kanthi K. Sarpatwar. Approximation algorithms for connected maximum cut and related problems. In Algorithms - ESA 2015 - 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings, pages 693-704, 2015. Google Scholar
  27. Chien-Chung Huang, Danupon Nanongkai, and Thatchaphol Saranurak. Distributed exact weighted all-pairs shortest paths in Õ(n^5/4) rounds. In IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 168-179, 2017. Google Scholar
  28. Hossein Jowhari, Mert Sağlam, and Gábor Tardos. Tight bounds for ?_p samplers, finding duplicates in streams, and related problems. In Proceedings of the Thirtieth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS '11, pages 49-58, New York, NY, USA, 2011. ACM. Google Scholar
  29. 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. Google Scholar
  30. Shahbaz Khan and Shashank Mehta. Depth first search in the semi-streaming model. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019. Google Scholar
  31. Daniel J. Kleitman and Douglas B. West. Spanning trees with many leaves. SIAM J. Discrete Math., 4(1):99-106, 1991. Google Scholar
  32. F. T. Leighton, B. M. Maggs, and S. B. Rao. Packet routing and job-shop scheduling in O(Congestion+Dilation) steps. Combinatorica, 14(2):167-186, 1994. Google Scholar
  33. R. Lipton and R. Tarjan. A separator theorem for planar graphs. SIAM Journal on Applied Mathematics, 36(2):177-189, 1979. Google Scholar
  34. Hsueh-I Lu and R. Ravi. The power of local optimization: Approximation algorithms for maximum-leaf spanning tree. In In Proceedings, Thirtieth Annual Allerton Conference on Communication, Control and Computing, pages 533-542, 1992. Google Scholar
  35. Hsueh-I Lu and R. Ravi. Approximating maximum leaf spanning trees in almost linear time. J. Algorithms, 29(1):132-141, 1998. Google Scholar
  36. Andrew McGregor, David Tench, Sofya Vorotnikova, and Hoa T. Vu. Densest subgraph in dynamic graph streams. In Mathematical Foundations of Computer Science 2015 - 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part II, pages 472-482, 2015. Google Scholar
  37. S. Muthukrishnan. Data streams: Algorithms and applications. Found. Trends Theor. Comput. Sci., 1(2):117-236, August 2005. Google Scholar
  38. Hiroshi Nagamochi and Toshihide Ibaraki. A linear-time algorithm for finding a sparse k-connected spanning subgraph of a k-connected graph. Algorithmica, 7(5&6):583-596, 1992. Google Scholar
  39. Jelani Nelson and Huacheng Yu. Optimal lower bounds for distributed and streaming spanning forest computation. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 1844-1860, 2019. Google Scholar
  40. Liam Roditty and Virginia Vassilevska Williams. Fast approximation algorithms for the diameter and radius of sparse graphs. In Proceedings 45th ACM Symposium on Theory of Computing (STOC), pages 515-524, 2013. Google Scholar
  41. Jens M. Schmidt. A simple test on 2-vertex- and 2-edge-connectivity. Inf. Process. Lett., 113(7):241-244, 2013. Google Scholar
  42. Roberto Solis-Oba, Paul S. Bonsma, and Stefanie Lowski. A 2-approximation algorithm for finding a spanning tree with maximum number of leaves. Algorithmica, 77(2):374-388, 2017. Google Scholar
  43. Xiaoming Sun and David P. Woodruff. Tight bounds for graph problems in insertion streams. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2015, August 24-26, 2015, Princeton, NJ, USA, pages 435-448, 2015. Google Scholar
  44. Robert Endre Tarjan. A note on finding the bridges of a graph. Inf. Process. Lett., 2(6):160-161, 1974. Google Scholar
  45. J. D. Ullman and M. Yannakakis. High-probability parallel transitive-closure algorithms. SIAM Journal on Computing, 20(1):100-125, 1991. 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