Document Open Access Logo

Near-Optimal Distributed Computation of Small Vertex Cuts

Authors Merav Parter, Asaf Petruschka

PDF
Thumbnail PDF

File

LIPIcs.DISC.2022.31.pdf
  • Filesize: 0.84 MB
  • 21 pages

Document Identifiers

Author Details

Merav Parter
  • Weizmann Institute, Rehovot, Israel
Asaf Petruschka
  • Weizmann Institute, Rehovot, Israel

Funding

  • Parter, Merav: Supported by the European Research Council (ERC) No. 949083), and by the Israeli Science Foundation (ISF) No. 2084/18.

Cite AsGet BibTex

Merav Parter and Asaf Petruschka. Near-Optimal Distributed Computation of Small Vertex Cuts. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 31:1-31:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.DISC.2022.31

Abstract

We present near-optimal algorithms for detecting small vertex cuts in the {CONGEST} model of distributed computing. Despite extensive research in this area, our understanding of the vertex connectivity of a graph is still incomplete, especially in the distributed setting. To this date, all distributed algorithms for detecting cut vertices suffer from an inherent dependency in the maximum degree of the graph, Δ. Hence, in particular, there is no truly sub-linear time algorithm for this problem, not even for detecting a single cut vertex. We take a new algorithmic approach for vertex connectivity which allows us to bypass the existing Δ barrier. - As a warm-up to our approach, we show a simple Õ(D)-round randomized algorithm for computing all cut vertices in a D-diameter n-vertex graph. This improves upon the O(D+Δ/log n)-round algorithm of [Pritchard and Thurimella, ICALP 2008]. - Our key technical contribution is an Õ(D)-round randomized algorithm for computing all cut pairs in the graph, improving upon the state-of-the-art O(Δ ⋅ D)⁴-round algorithm by [Parter, DISC '19]. Note that even for the considerably simpler setting of edge cuts, currently Õ(D)-round algorithms are currently known only for detecting pairs of cut edges. Our approach is based on employing the well-known linear graph sketching technique [Ahn, Guha and McGregor, SODA 2012] along with the heavy-light tree decomposition of [Sleator and Tarjan, STOC 1981] . Combining this with a careful characterization of the survivable subgraphs, allows us to determine the connectivity of G ⧵ {x,y} for every pair x,y ∈ V, using Õ(D)-rounds. We believe that the tools provided in this paper are useful for omitting the Δ-dependency even for larger cut values.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
  • Theory of computation → Graph algorithms analysis
Keywords
  • Vertex-connectivity
  • Congest
  • Graph Sketches

Metrics

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

Related Versions

References

  1. 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, pages 459-467. SIAM, 2012. Google Scholar
  2. Giuseppe Di Battista and Roberto Tamassia. Incremental planarity testing (extended abstract). In 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October - 1 November 1989, pages 436-441. IEEE Computer Society, 1989. Google Scholar
  3. Giuseppe Di Battista and Roberto Tamassia. On-line maintenance of triconnected components with spqr-trees. Algorithmica, 15(4):302-318, 1996. Google Scholar
  4. Keren Censor-Hillel, Mohsen Ghaffari, and Fabian Kuhn. Distributed connectivity decomposition. In Proceedings of the 2014 ACM symposium on Principles of distributed computing, pages 156-165. ACM, 2014. Google Scholar
  5. Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva. Maximum flow and minimum-cost flow in almost-linear time. CoRR, abs/2203.00671, 2022. URL: https://doi.org/10.48550/arXiv.2203.00671.
  6. Keerti Choudhary. An optimal dual fault tolerant reachability oracle. In Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi, editors, 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, volume 55 of LIPIcs, pages 130:1-130:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. Google Scholar
  7. Michal Dory, Yuval Efron, Sagnik Mukhopadhyay, and Danupon Nanongkai. Distributed weighted min-cut in nearly-optimal time. In Samir Khuller and Virginia Vassilevska Williams, editors, STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 1144-1153. ACM, 2021. Google Scholar
  8. Michal Dory and Merav Parter. Fault-tolerant labeling and compact routing schemes. In Avery Miller, Keren Censor-Hillel, and Janne H. Korhonen, editors, PODC '21: ACM Symposium on Principles of Distributed Computing, Virtual Event, Italy, July 26-30, 2021, pages 445-455. ACM, 2021. Google Scholar
  9. Ran Duan and Seth Pettie. Dual-failure distance and connectivity oracles. In Proceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms, pages 506-515. SIAM, 2009. Google Scholar
  10. Ran Duan and Seth Pettie. Connectivity oracles for graphs subject to vertex failures. CoRR, abs/1607.06865, 2016. URL: http://arxiv.org/abs/1607.06865.
  11. Ran Duan and Seth Pettie. Connectivity oracles for graphs subject to vertex failures. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 490-509, 2017. Google Scholar
  12. Pawel Gawrychowski, Shay Mozes, and Oren Weimann. Minimum cut in o(m log² n) time. In Artur Czumaj, Anuj Dawar, and Emanuela Merelli, editors, 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference), volume 168 of LIPIcs, pages 57:1-57:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. Google Scholar
  13. Loukas Georgiadis, Giuseppe F. Italiano, Luigi Laura, and Nikos Parotsidis. 2-vertex connectivity in directed graphs. In Magnús M. Halldórsson, Kazuo Iwama, Naoki Kobayashi, and Bettina Speckmann, editors, Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, volume 9134 of Lecture Notes in Computer Science, pages 605-616. Springer, 2015. Google Scholar
  14. Mohsen Ghaffari. Near-optimal scheduling of distributed algorithms. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC, pages 3-12, 2015. Google Scholar
  15. Mohsen Ghaffari and Bernhard Haeupler. Distributed algorithms for planar networks II: low-congestion shortcuts, MST, and min-cut. 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 202-219. SIAM, 2016. Google Scholar
  16. Mohsen Ghaffari, Krzysztof Nowicki, and Mikkel Thorup. Faster algorithms for edge connectivity via random 2-out contractions. 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 1260-1279. SIAM, 2020. Google Scholar
  17. Mohsen Ghaffari and Merav Parter. MST in log-star rounds of congested clique. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC 2016, Chicago, IL, USA, July 25-28, 2016, pages 19-28, 2016. Google Scholar
  18. David Gibb, Bruce M. Kapron, Valerie King, and Nolan Thorn. Dynamic graph connectivity with improved worst case update time and sublinear space. CoRR, abs/1509.06464, 2015. URL: http://arxiv.org/abs/1509.06464.
  19. Manoj Gupta and Shahbaz Khan. Multiple source dual fault tolerant BFS trees. In Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl, editors, 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, volume 80 of LIPIcs, pages 127:1-127:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. Google Scholar
  20. Zhiyang He, Jason Li, and Magnus Wahlström. Near-linear-time, optimal vertex cut sparsifiers in directed acyclic graphs. In Petra Mutzel, Rasmus Pagh, and Grzegorz Herman, editors, 29th Annual European Symposium on Algorithms, ESA 2021, September 6-8, 2021, Lisbon, Portugal (Virtual Conference), volume 204 of LIPIcs, pages 52:1-52:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. Google Scholar
  21. John E. Hopcroft and Robert Endre Tarjan. Dividing a graph into triconnected components. SIAM J. Comput., 2(3):135-158, 1973. Google Scholar
  22. Michael Kapralov and David Woodruff. Spanners and sparsifiers in dynamic streams. In Proceedings of the 2014 ACM symposium on Principles of distributed computing, pages 272-281, 2014. Google Scholar
  23. Bruce M Kapron, Valerie King, and Ben Mountjoy. Dynamic graph connectivity in polylogarithmic worst case time. In Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms, pages 1131-1142. SIAM, 2013. Google Scholar
  24. David R Karger. Random sampling in cut, flow, and network design problems. Mathematics of Operations Research, 24(2):383-413, 1999. Google Scholar
  25. Karthik C. S. and Merav Parter. Deterministic replacement path covering. In Dániel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10-13, 2021, pages 704-723. SIAM, 2021. Google Scholar
  26. Valerie King, Shay Kutten, and Mikkel Thorup. Construction and impromptu repair of an MST in a distributed network with o(m) communication. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC 2015, Donostia-San Sebastián, Spain, July 21-23, 2015, pages 71-80, 2015. Google Scholar
  27. Frank Thomson Leighton, Bruce M Maggs, and Satish B Rao. Packet routing and job-shop scheduling ino (congestion+ dilation) steps. Combinatorica, 14(2):167-186, 1994. Google Scholar
  28. Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak, and Sorrachai Yingchareonthawornchai. Vertex connectivity in poly-logarithmic max-flows. In Samir Khuller and Virginia Vassilevska Williams, editors, STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 317-329. ACM, 2021. Google Scholar
  29. Ali Mashreghi and Valerie King. Broadcast and minimum spanning tree with o(m) messages in the asynchronous CONGEST model. In 32nd International Symposium on Distributed Computing, DISC 2018, New Orleans, LA, USA, October 15-19, 2018, pages 37:1-37:17, 2018. Google Scholar
  30. Danupon Nanongkai, Thatchaphol Saranurak, and Sorrachai Yingchareonthawornchai. Breaking quadratic time for small vertex connectivity and an approximation scheme. In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 241-252. ACM, 2019. Google Scholar
  31. Jaroslav Nešetřil, Eva Milková, and Helena Nešetřilová. Otakar Borůvka on minimum spanning tree problem translation of both the 1926 papers, comments, history. Discrete Mathematics, 233(1):3-36, 2001. Google Scholar
  32. Merav Parter. Dual failure resilient BFS structure. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, pages 481-490, 2015. Google Scholar
  33. Merav Parter. Small cuts and connectivity certificates: A fault tolerant approach. In 33rd International Symposium on Distributed Computing, 2019. Google Scholar
  34. Merav Parter. Distributed constructions of dual-failure fault-tolerant distance preservers. In Hagit Attiya, editor, 34th International Symposium on Distributed Computing, DISC 2020, October 12-16, 2020, Virtual Conference, volume 179 of LIPIcs, pages 21:1-21:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. Google Scholar
  35. David Peleg. Distributed Computing: A Locality-sensitive Approach. SIAM, 2000. Google Scholar
  36. Seth Pettie and Longhui Yin. The structure of minimum vertex cuts. In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12-16, 2021, Glasgow, Scotland (Virtual Conference), volume 198 of LIPIcs, pages 105:1-105:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. Google Scholar
  37. David Pritchard and Ramakrishna Thurimella. Fast computation of small cuts via cycle space sampling. ACM Transactions on Algorithms (TALG), 7(4):46, 2011. Google Scholar
  38. Daniel Dominic Sleator and Robert Endre Tarjan. A data structure for dynamic trees. J. Comput. Syst. Sci., 26(3):362-391, 1983. Google Scholar
  39. Robert Endre Tarjan. Depth-first search and linear graph algorithms. SIAM J. Comput., 1(2):146-160, 1972. Google Scholar
  40. Ramakrishna Thurimella. Sub-linear distributed algorithms for sparse certificates and biconnected components. Journal of Algorithms, 23(1):160-179, 1997. Google Scholar
  41. Salil P. Vadhan. Pseudorandomness. Foundations and Trends® in Theoretical Computer Science, 7(1–3):1-336, 2012. URL: https://doi.org/10.1561/0400000010.
  42. Oren Weimann and Raphael Yuster. Replacement paths and distance sensitivity oracles via fast matrix multiplication. ACM Transactions on Algorithms (TALG), 9(2):14, 2013. 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