Document Open Access Logo

A Distributed Algorithm for Directed Minimum-Weight Spanning Tree

Authors Orr Fischer, Rotem Oshman

PDF
Thumbnail PDF

File

LIPIcs.DISC.2019.16.pdf
  • Filesize: 0.55 MB
  • 16 pages

Document Identifiers

Author Details

Orr Fischer
  • Computer Science Department, Tel-Aviv University, Israel
Rotem Oshman
  • Computer Science Department, Tel-Aviv University, Israel

Funding

  • Fischer, Orr: Research supported by the Israeli Centers of Research Excellence (I-CORE) program (Center No. 4/11) and the Laura Schwarz-Kipp Institute of Computer Networks.
  • Oshman, Rotem: Research supported by the Israeli Centers of Research Excellence (I-CORE) program (Center No. 4/11).

Cite AsGet BibTex

Orr Fischer and Rotem Oshman. A Distributed Algorithm for Directed Minimum-Weight Spanning Tree. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 16:1-16:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.DISC.2019.16

Abstract

In the directed minimum spanning tree problem (DMST, also called minimum weight arborescence), the network is given a root node r, and needs to construct a minimum-weight directed spanning tree, rooted at r and oriented outwards. In this paper we present the first sub-quadratic DMST algorithms in the distributed CONGEST network model, where the messages exchanged between the network nodes are bounded in size. We consider three versions: a model where the communication links are bidirectional but can have different weights in the two directions; a model where communication is unidirectional; and the Congested Clique model, where all nodes can communicate directly with each other. Our algorithm is based on a variant of Lovász' DMST algorithm for the PRAM model, and uses a distributed single-source shortest-path (SSSP) algorithm for directed graphs as a black box. In the bidirectional CONGEST model, our algorithm has roughly the same running time as the SSSP algorithm; using the state-of-the-art SSSP algorithm, we obtain a running time of O~(min(sqrt{nD},sqrt{n}D^{1/4} + n^{3/5} +D)) rounds for the bidirectional communication case. For the unidirectional communication model we give an O~(n) algorithm, and show that it is nearly optimal. And finally, for the Congested Clique, our algorithm again matches the best known SSSP algorithm: it runs in O~(n^{1/3}) rounds. On the negative side, we adapt an observation of Chechik in the sequential setting to show that in all three models, the DMST problem is at least as hard as the (s,t)-shortest path problem. Thus, in terms of round complexity, distributed DMST lies between single-source shortest path and (s,t)-shortest path.

Subject Classification

ACM Subject Classification
  • Networks → Network algorithms
  • Theory of computation → Distributed algorithms
Keywords
  • Distributed Computing
  • Directed Minimum Spanning Tree
  • Minimum Arborescence
  • CONGEST

Metrics

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

Related Versions

References

  1. Aaron Bernstein and Danupon Nanongkai. Distributed Exact Weighted All-Pairs Shortest Paths in Near-Linear Time. In Proceedings of the 51th Annual ACM SIGACT Symposium on Theory of Computing, STOC '19, 2019. Google Scholar
  2. F. Bock. An algorithm to construct a minimum directed spanning tree in a directed network. In Developments in Operations Research, pages 29-44, 1971. Google Scholar
  3. Keren Censor-Hillel, Petteri Kaski, Janne H. Korhonen, Christoph Lenzen, Ami Paz, and Jukka Suomela. Algebraic Methods in the Congested Clique. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC 2015, pages 143-152, 2015. Google Scholar
  4. S. Chechik. Private Communication. Google Scholar
  5. Mohit Daga, Monika Henzinger, Danupon Nanongkai, and Thatchaphol Saranurak. Distributed Edge Connectivity in Sublinear Time. In Proceedings of the 51th Annual ACM SIGACT Symposium on Theory of Computing, STOC '19, 2019. Google Scholar
  6. Tarjan R. E. Finding optimum branchings. Networks, 7(1):25-35, 1965. Google Scholar
  7. Jack Edmonds. Optimum branchings. Journal of Research of the National Bureau of Standards, 71B(4):233-240, 1967. Google Scholar
  8. M. Elkin. An Unconditional Lower Bound on the Time-Approximation Trade-off for the Distributed Minimum Spanning Tree Problem. SIAM Journal on Computing, 36(2):433-456, 2006. Google Scholar
  9. Michael Elkin. A faster distributed protocol for constructing a minimum spanning tree. J. Comput. Syst. Sci., 72(8):1282-1308, 2006. Google Scholar
  10. Michael Elkin. A Simple Deterministic Distributed MST Algorithm, with Near-Optimal Time and Message Complexities. In Proceedings of the ACM Symposium on Principles of Distributed Computing, (PODC), pages 157-163, 2017. Google Scholar
  11. Orr Fischer and Rotem Oshman. A Distributed Algorithm for Directed Minimum-Weight Spanning Tree. URL: https://www.cs.tau.ac.il/~roshman/papers/DISC19_FO.pdf.
  12. Sebastian Forster and Danupon Nanongkai. A Faster Distributed Single-Source Shortest Paths Algorithm. In 59th IEEE Annual Symposium on Foundations of Computer Science, (FOCS), pages 686-697, 2018. Google Scholar
  13. H N Gabow, Z Galil, T Spencer, and R E Tarjan. Efficient Algorithms for Finding Minimum Spanning Trees in Undirected and Directed Graphs. Combinatorica, 6(2):109-122, January 1986. Google Scholar
  14. J. A. Garay, S. Kutten, and D. Peleg. A sub-linear time distributed algorithm for minimum-weight spanning trees. In Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science, pages 659-668, 1993. Google Scholar
  15. Mohsen Ghaffari and Bernhard Haeupler. Distributed Algorithms for Planar Networks II: Low-Congestion Shortcuts, MST, and Min-Cut. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 202-219, 2016. Google Scholar
  16. 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, pages 431-444, 2018. 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, pages 19-28, 2016. Google Scholar
  18. Bernhard Haeupler, Taisuke Izumi, and Goran Zuzic. Low-Congestion Shortcuts without Embedding. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing (PODC) 2016, pages 451-460, 2016. Google Scholar
  19. Bernhard Haeupler and Jason Li. Faster Distributed Shortest Path Approximations via Shortcuts. In 32nd International Symposium on Distributed Computing, (DISC) 2018, pages 33:1-33:14, 2018. Google Scholar
  20. Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. A Deterministic Almost-tight Distributed Algorithm for Approximating Single-source Shortest Paths. In Proceedings of the Forty-eighth Annual ACM Symposium on Theory of Computing, STOC '16, pages 489-498, 2016. Google Scholar
  21. P. Humblet. A Distributed Algorithm for Minimum Weight Directed Spanning Trees. IEEE Transactions on Communications, 31(6):756-762, 1983. Google Scholar
  22. Tomasz Jurdzinski and Krzysztof Nowicki. MST in O(1) rounds of congested clique. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, pages 2620-2632, 2018. Google Scholar
  23. Zvi Lotker, Boaz Patt-Shamir, Elan Pavlov, and David Peleg. Minimum-Weight Spanning Tree Construction in O(log log n) Communication Rounds. SIAM J. Comput., 35(1):120-131, 2005. Google Scholar
  24. L. Lovasz. Computing ears and branchings in parallel. In 26th Annual Symposium on Foundations of Computer Science (sfcs 1985)(FOCS), volume 00, pages 464-467, 1985. Google Scholar
  25. Danupon Nanongkai. Distributed Approximation Algorithms for Weighted Shortest Paths. In Proceedings of the Forty-sixth Annual ACM Symposium on Theory of Computing, STOC '14, pages 565-573, 2014. Google Scholar
  26. Gopal Pandurangan, Peter Robinson, and Michele Scquizzato. A Time- and Message-optimal Distributed Algorithm for Minimum Spanning Trees. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, pages 743-756, 2017. Google Scholar
  27. D. Peleg and V. Rubinovich. A near-tight lower bound on the time complexity of distributed MST construction. In 40th Annual Symposium on Foundations of Computer Science (FOCS), pages 253-261, 1999. Google Scholar
  28. F. Maffioli P.M. Camerini, L. Fratta. A note on finding optimum branchings. Networks, 7:309–-312, 1979. Google Scholar
  29. F. Maffioli P.M. Camerini, L. Fratta. The k best spanning arborescences of a network. Networks, 10(2):91–-109, 1980. Google Scholar
  30. Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Pandurangan, David Peleg, and Roger Wattenhofer. Distributed Verification and Hardness of Distributed Approximation. SIAM J. Comput., 41(5):1235-1265, 2012. Google Scholar
  31. Ramakrishna Thurimella. Sub-linear Distributed Algorithms for Sparse Certificates and Biconnected Components. In Proceedings of the Fourteenth Annual ACM Symposium on Principles of Distributed Computing, PODC '95, 1995. Google Scholar
  32. T.H. Liu. Y.J. Chu. On the shortest arborescence of a directed graph. Sci. Sinica, 14(2):1396-1400, 1965. 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