Document Open Access Logo

Log Diameter Rounds Algorithms for 2-Vertex and 2-Edge Connectivity

Authors Alexandr Andoni, Clifford Stein, Peilin Zhong

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2019.14.pdf
  • Filesize: 0.52 MB
  • 16 pages

Document Identifiers

Author Details

Alexandr Andoni
  • Columbia University, New York City, NY, USA
Clifford Stein
  • Columbia University, New York City, NY, USA
Peilin Zhong
  • Columbia University, New York City, NY, USA

Funding

  • Andoni, Alexandr: Research partly supported by NSF Grants (CCF-1617955 and CCF-1740833), Simons Foundation (#491119) and Google Research Award.
  • Stein, Clifford: Research partly supported by NSF Grants CCF-1714818 and CCF-1822809.
  • Zhong, Peilin: Research partly supported by NSF Grants (CCF-1703925, CCF-1421161, CCF-1714818, CCF-1617955 and CCF-1740833), Simons Foundation (#491119) and Google Research Award.

Cite AsGet BibTex

Alexandr Andoni, Clifford Stein, and Peilin Zhong. Log Diameter Rounds Algorithms for 2-Vertex and 2-Edge Connectivity. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 14:1-14:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ICALP.2019.14

Abstract

Many modern parallel systems, such as MapReduce, Hadoop and Spark, can be modeled well by the MPC model. The MPC model captures well coarse-grained computation on large data - data is distributed to processors, each of which has a sublinear (in the input data) amount of memory and we alternate between rounds of computation and rounds of communication, where each machine can communicate an amount of data as large as the size of its memory. This model is stronger than the classical PRAM model, and it is an intriguing question to design algorithms whose running time is smaller than in the PRAM model. In this paper, we study two fundamental problems, 2-edge connectivity and 2-vertex connectivity (biconnectivity). PRAM algorithms which run in O(log n) time have been known for many years. We give algorithms using roughly log diameter rounds in the MPC model. Our main results are, for an n-vertex, m-edge graph of diameter D and bi-diameter D', 1) a O(log D log log_{m/n} n) parallel time 2-edge connectivity algorithm, 2) a O(log D log^2 log_{m/n}n+log D'log log_{m/n}n) parallel time biconnectivity algorithm, where the bi-diameter D' is the largest cycle length over all the vertex pairs in the same biconnected component. Our results are fully scalable, meaning that the memory per processor can be O(n^{delta}) for arbitrary constant delta>0, and the total memory used is linear in the problem size. Our 2-edge connectivity algorithm achieves the same parallel time as the connectivity algorithm of [Andoni et al., 2018]. We also show an Omega(log D') conditional lower bound for the biconnectivity problem.

Subject Classification

ACM Subject Classification
  • Theory of computation → MapReduce algorithms
  • Mathematics of computing → Paths and connectivity problems
Keywords
  • parallel algorithms
  • biconnectivity
  • 2-edge connectivity
  • the MPC model

Metrics

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

Related Versions

References

  1. Kook Jin Ahn and Sudipto Guha. Access to data and number of iterations: Dual primal algorithms for maximum matching under resource constraints. ACM Transactions on Parallel Computing (TOPC), 4(4):17, 2018. Google Scholar
  2. Noga Alon, László Babai, and Alon Itai. A fast and simple randomized parallel algorithm for the maximal independent set problem. Journal of algorithms, 7(4):567-583, 1986. Google Scholar
  3. Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak, and Grigory Yaroslavtsev. Parallel algorithms for geometric graph problems. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 574-583. ACM, 2014. Google Scholar
  4. Alexandr Andoni, Zhao Song, Clifford Stein, Zhengyu Wang, and Peilin Zhong. Parallel Graph Connectivity in Log Diameter Rounds, 2018. In FOCS 2018. URL: http://arxiv.org/abs/1805.03055.
  5. Sepehr Assadi, MohammadHossein Bateni, Aaron Bernstein, Vahab Mirrokni, and Cliff Stein. Coresets meet EDCS: algorithms for matching and vertex cover on massive graphs. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1616-1635. SIAM, 2019. Google Scholar
  6. Sepehr Assadi and Sanjeev Khanna. Randomized composable coresets for matching and vertex cover. In Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures, pages 3-12. ACM, 2017. Google Scholar
  7. Sepehr Assadi, Xiaorui Sun, and Omri Weinstein. Massively Parallel Algorithms for Finding Well-Connected Components in Sparse Graphs. arXiv preprint, 2018. URL: http://arxiv.org/abs/1805.02974.
  8. Giorgio Ausiello, Donatella Firmani, Luigi Laura, and Emanuele Paracone. Large-scale graph biconnectivity in MapReduce. Department of Computer and System Sciences Antonio Ruberti Technical Reports, 4(4), 2012. Google Scholar
  9. Boaz Barak, Jonathan A Kelner, and David Steurer. Dictionary learning and tensor decomposition via the sum-of-squares method. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing (STOC), pages 143-151. ACM, 2015. URL: http://arxiv.org/abs/1407.1543.
  10. Paul Beame and Johan Hastad. Optimal bounds for decision problems on the CRCW PRAM. Journal of the ACM (JACM), 36(3):643-670, 1989. Google Scholar
  11. Paul Beame, Paraschos Koutris, and Dan Suciu. Communication steps for parallel query processing. In Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGAI symposium on Principles of database systems, pages 273-284. ACM, 2013. Google Scholar
  12. Soheil Behnezhad, Mahsa Derakhshan, and MohammadTaghi Hajiaghayi. Brief announcement: Semi-mapreduce meets congested clique. arXiv preprint, 2018. URL: http://arxiv.org/abs/1802.10297.
  13. Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, and Richard M Karp. Massively parallel symmetry breaking on sparse graphs: MIS and maximal matching. arXiv preprint, 2018. URL: http://arxiv.org/abs/1807.06701.
  14. Sebastian Brandt, Manuela Fischer, and Jara Uitto. Matching and MIS for Uniformly Sparse Graphs in the Low-Memory MPC Model. arXiv preprint, 2018. URL: http://arxiv.org/abs/1807.05374.
  15. Artur Czumaj, Jakub Łącki, Aleksander Mądry, Slobodan Mitrović, Krzysztof Onak, and Piotr Sankowski. Round compression for parallel matching algorithms. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 471-484. ACM, 2018. Google Scholar
  16. Jeffrey Dean and Sanjay Ghemawat. MapReduce: Simplified Data Processing on Large Clusters. To appear in OSDI, page 1, 2004. Google Scholar
  17. Jeffrey Dean and Sanjay Ghemawat. MapReduce: simplified data processing on large clusters. Communications of the ACM, 51(1):107-113, 2008. Google Scholar
  18. Reinhard Diestel. Graph theory. Springer Publishing Company, Incorporated, 2018. Google Scholar
  19. Alina Ene, Sungjin Im, and Benjamin Moseley. Fast clustering using MapReduce. In Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 681-689. ACM, 2011. Google Scholar
  20. Manuela Fischer, Mohsen Ghaffari, and Jara Uitto. Simple Graph Coloring Algorithms for Congested Clique and Massively Parallel Computation. arXiv preprint, 2018. URL: http://arxiv.org/abs/1808.08419.
  21. Michael T Goodrich, Nodari Sitchinava, and Qin Zhang. Sorting, Searching, and Simulation in the MapReduce Framework. In ISAAC, volume 7074, pages 374-383. Springer, 2011. Google Scholar
  22. Sungjin Im, Benjamin Moseley, and Xiaorui Sun. Efficient massively parallel methods for dynamic programming. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 798-811. ACM, 2017. Google Scholar
  23. Michael Isard, Mihai Budiu, Yuan Yu, Andrew Birrell, and Dennis Fetterly. Dryad: distributed data-parallel programs from sequential building blocks. In ACM SIGOPS operating systems review, volume 41 (3), pages 59-72. ACM, 2007. Google Scholar
  24. Tomasz Jurdziński and Krzysztof Nowicki. MST in O(1) rounds of congested clique. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2620-2632. SIAM, 2018. Google Scholar
  25. Howard Karloff, Siddharth Suri, and Sergei Vassilvitskii. A model of computation for MapReduce. In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms, pages 938-948. Society for Industrial and Applied Mathematics, 2010. Google Scholar
  26. Richard M Karp, Eli Upfal, and Avi Wigderson. Constructing a perfect matching is in random NC. Combinatorica, 6(1):35-48, 1986. Google Scholar
  27. Valerie King, Chung Keung Poon, Vijaya Ramachandran, and Santanu Sinha. An optimal EREW PRAM algorithm for minimum spanning tree verification. Information Processing Letters, 62(3):153-159, 1997. Google Scholar
  28. Raimondas Kiveris, Silvio Lattanzi, Vahab Mirrokni, Vibhor Rastogi, and Sergei Vassilvitskii. Connected components in mapreduce and beyond. In Proceedings of the ACM Symposium on Cloud Computing, pages 1-13. ACM, 2014. Google Scholar
  29. Silvio Lattanzi, Benjamin Moseley, Siddharth Suri, and Sergei Vassilvitskii. Filtering: a method for solving graph problems in mapreduce. In Proceedings of the twenty-third annual ACM symposium on Parallelism in algorithms and architectures, pages 85-94. ACM, 2011. Google Scholar
  30. Sixue Liu and Robert E Tarjan. Simple Concurrent Labeling Algorithms for Connected Components. arXiv preprint, 2018. URL: http://arxiv.org/abs/1812.06177.
  31. Michael Luby. A simple parallel algorithm for the maximal independent set problem. SIAM journal on computing, 15(4):1036-1053, 1986. Google Scholar
  32. Krzysztof Onak. Round compression for parallel graph algorithms in strongly sublinear space. arXiv preprint, 2018. URL: http://arxiv.org/abs/1807.08745.
  33. John H Reif. Optimal Parallel Algorithms for Interger Sorting and Graph Connectivity. Technical report, HARVARD UNIV CAMBRIDGE MA AIKEN COMPUTATION LAB, 1985. Google Scholar
  34. Tim Roughgarden, Sergei Vassilvitskii, and Joshua R Wang. Shuffles and circuits:(on lower bounds for modern parallel computation). In Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures, pages 1-12. ACM, 2016. Google Scholar
  35. Yossi Shiloach and Uzi Vishkin. An O (log n) parallel connectivity algorithm. Technical report, Computer Science Department, Technion, 1980. Google Scholar
  36. Robert E Tarjan and Uzi Vishkin. An efficient parallel biconnectivity algorithm. SIAM Journal on Computing, 14(4):862-874, 1985. Google Scholar
  37. Robert Endre Tarjan and Uzi Vishkin. Finding biconnected componemts and computing tree functions in logarithmic parallel time. In 25th Annual Symposium onFoundations of Computer Science, 1984., pages 12-20. IEEE, 1984. Google Scholar
  38. Leslie G Valiant. A bridging model for parallel computation. Communications of the ACM, 33(8):103-111, 1990. Google Scholar
  39. Virginia Vassilevska Williams. Multiplying matrices faster than Coppersmith-Winograd. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing (STOC), pages 887-898. ACM, 2012. Google Scholar
  40. Grigory Yaroslavtsev and Adithya Vadapalli. Massively Parallel Algorithms and Hardness for Single-Linkage Clustering under Lp Distances. In International Conference on Machine Learning, pages 5596-5605, 2018. Google Scholar
  41. Matei Zaharia, Mosharaf Chowdhury, Michael J Franklin, Scott Shenker, and Ion Stoica. Spark: Cluster computing with working sets. HotCloud, 10(10-10):95, 2010. 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact