Document Open Access Logo

Low-Congestion Shortcut and Graph Parameters

Authors Naoki Kitamura, Hirotaka Kitagawa, Yota Otachi, Taisuke Izumi

PDF
Thumbnail PDF

File

LIPIcs.DISC.2019.25.pdf
  • Filesize: 0.81 MB
  • 17 pages

Document Identifiers

Author Details

Naoki Kitamura
  • Nagoya Institute of Technology, Japan
Hirotaka Kitagawa
  • Nagoya Institute of Technology, Japan
Yota Otachi
  • Kumamoto University, Japan
Taisuke Izumi
  • Nagoya Institute of Technology, Japan

Acknowledgements

This work was supported by JSPS KAKENHI Grant Numbers JP18H04091, JP18K11168, JP18K11169, JP19K11824, and JP19J22696, and JST SICORP Grant Number JPMJSC1606, Japan.

Cite As Get BibTex

Naoki Kitamura, Hirotaka Kitagawa, Yota Otachi, and Taisuke Izumi. Low-Congestion Shortcut and Graph Parameters. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.DISC.2019.25

Abstract

Distributed graph algorithms in the standard CONGEST model often exhibit the time-complexity lower bound of Omega~(sqrt{n} + D) rounds for many global problems, where n is the number of nodes and D is the diameter of the input graph. Since such a lower bound is derived from special "hard-core" instances, it does not necessarily apply to specific popular graph classes such as planar graphs. The concept of low-congestion shortcuts is initiated by Ghaffari and Haeupler [SODA2016] for addressing the design of CONGEST algorithms running fast in restricted network topologies. Specifically, given a specific graph class X, an f-round algorithm of constructing shortcuts of quality q for any instance in X results in O~(q + f)-round algorithms of solving several fundamental graph problems such as minimum spanning tree and minimum cut, for X. The main interest on this line is to identify the graph classes allowing the shortcuts which are efficient in the sense of breaking O~(sqrt{n}+D)-round general lower bounds.
In this paper, we consider the relationship between the quality of low-congestion shortcuts and three major graph parameters, chordality, diameter, and clique-width. The main contribution of the paper is threefold: (1) We show an O(1)-round algorithm which constructs a low-congestion shortcut with quality O(kD) for any k-chordal graph, and prove that the quality and running time of this construction is nearly optimal up to polylogarithmic factors. (2) We present two algorithms, each of which constructs a low-congestion shortcut with quality O~(n^{1/4}) in O~(n^{1/4}) rounds for graphs of D=3, and that with quality O~(n^{1/3}) in O~(n^{1/3}) rounds for graphs of D=4 respectively. These results obviously deduce two MST algorithms running in O~(n^{1/4}) and O~(n^{1/3}) rounds for D=3 and 4 respectively, which almost close the long-standing complexity gap of the MST construction in small-diameter graphs originally posed by Lotker et al. [Distributed Computing 2006]. (3) We show that bounding clique-width does not help the construction of good shortcuts by presenting a network topology of clique-width six where the construction of MST is as expensive as the general case.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
Keywords
  • distributed graph algorithms
  • low-congestion shortcut
  • k-chordal graph
  • clique width
  • minimum spanning tree

Metrics

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

References

  1. Amir Abboud, Keren Censor-Hillel, and Seri Khoury. Near-Linear Lower Bounds for Distributed Distance Computations, Even in Sparse Networks. In Proceedings of 30nd International Symposium on Distributed Computing (DISC), pages 29-42, 2016. URL: https://doi.org/10.1007/978-3-662-53426-7_3.
  2. Baruch Awerbuch, Andrew V. Goldberg, Michael Luby, and Serge A. Plotkin. Network Decomposition and Locality in Distributed Computation. In Proceedings of 30th Annual Symposium on Foundations of Computer Science (FOCS), pages 364-369, 1989. URL: https://doi.org/10.1109/SFCS.1989.63504.
  3. Derek G. Corneil and Udi Rotics. On the Relationship Between Clique-Width and Treewidth. SIAM Journal on Computing, pages 825-847, 2005. URL: https://doi.org/10.1137/S0097539701385351.
  4. Bruno Courcelle and Stephan Olariu. Upper bounds to the clique width of graphs. Discrete Applied Mathematics, pages 77-114, 2000. URL: https://doi.org/10.1016/S0166-218X(99)00184-5.
  5. Michael Elkin. Distributed approximation: a survey. ACM SIGACT News, pages 40-57, 2004. URL: https://doi.org/10.1145/1054916.1054931.
  6. Michael Elkin. An Unconditional Lower Bound on the Time-Approximation Trade-off for the Distributed Minimum Spanning Tree Problem. SIAM Journal on Computing, pages 433-456, 2006. URL: https://doi.org/10.1137/S0097539704441058.
  7. Robert G. Gallager, Pierre A. Humblet, and Philip M. Spira. A Distributed Algorithm for Minimum-Weight Spanning Trees. ACM Transactions on Programming Languages and Systems (TOPLAS), pages 66-77, 1983. URL: https://doi.org/10.1145/357195.357200.
  8. Juan A. Garay, Shay Kutten, and David Peleg. A Sublinear Time Distributed Algorithm for Minimum-Weight Spanning Trees. SIAM Journal on Computing, pages 302-316, 1998. URL: https://doi.org/10.1137/S0097539794261118.
  9. Fǎnicǎ Gavril. The intersection graphs of subtrees in trees are exactly the chordal graphs. Journal of Combinatorial Theory, Series B, pages 47-56, 1974. URL: https://doi.org/10.1016/0095-8956(74)90094-X.
  10. 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. URL: https://doi.org/10.1145/2767386.2767417.
  11. 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. URL: https://doi.org/10.1137/1.9781611974331.ch16.
  12. Mohsen Ghaffari and Fabian Kuhn. Distributed MST and Broadcast with Fewer Messages, and Faster Gossiping. In Proceedings of 32nd International Symposium on Distributed Computing (DISC), pages 30:1-30:12, 2018. URL: https://doi.org/10.4230/LIPIcs.DISC.2018.30.
  13. Mohsen Ghaffari, Fabian Kuhn, and Hsin-Hao Su. Distributed MST and Routing in Almost Mixing Time. In Proceedings of 31nd International Symposium on Distributed Computing (DISC), pages 131-140, 2017. URL: https://doi.org/10.1145/3087801.3087827.
  14. Mohsen Ghaffari and Jason Li. New Distributed Algorithms in Almost Mixing Time via Transformations from Parallel Algorithms. In Proceedings of 32nd International Symposium on Distributed Computing (DISC), pages 31:1-31:16, 2018. URL: https://doi.org/10.4230/LIPIcs.DISC.2018.31.
  15. Robert Gmyr and Gopal Pandurangan. Time-Message Trade-Offs in Distributed Algorithms. In Proceedings of 32nd International Symposium on Distributed Computing (DISC), pages 32:1-32:18, 2018. URL: https://doi.org/10.4230/LIPIcs.DISC.2018.32.
  16. Bernhard Haeupler, D. Ellis Hershkowitz, and David Wajc. Round- and Message-Optimal Distributed Graph Algorithms. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing (PODC), pages 119-128, 2018. URL: https://doi.org/10.1145/3212734.3212737.
  17. 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), pages 451-460, 2016. URL: https://doi.org/10.1145/2933057.2933112.
  18. Bernhard Haeupler, Taisuke Izumi, and Goran Zuzic. Near-Optimal Low-Congestion Shortcuts on Bounded Parameter Graphs. In Proceedings of 30nd International Symposium on Distributed Computing (DISC), pages 158-172, 2016. URL: https://doi.org/10.1007/978-3-662-53426-7_12.
  19. Bernhard Haeupler and Jason Li. Faster Distributed Shortest Path Approximations via Shortcuts. In Proceedings of 32nd International Symposium on Distributed Computing (DISC), pages 33:1-33:14, 2018. URL: https://doi.org/10.4230/LIPIcs.DISC.2018.33.
  20. Bernhard Haeupler, Jason Li, and Goran Zuzic. Minor Excluded Network Families Admit Fast Distributed Algorithms. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing (PODC), pages 465-474, 2018. URL: https://doi.org/10.1145/3212734.3212776.
  21. 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), pages 2620-2632, 2018. URL: https://doi.org/10.1137/1.9781611975031.167.
  22. Shay Kutten and David Peleg. Fast Distributed Construction of Small k-Dominating Sets and Applications. Journal of Algorithms, pages 40-66, 1998. URL: https://doi.org/10.1006/jagm.1998.0929.
  23. Jason Li. Distributed Treewidth Computation. arXiv, 2018. URL: http://arxiv.org/abs/1805.10708.
  24. Zvi Lotker, Boaz Patt-Shamir, and David Peleg. Distributed MST for constant diameter graphs. Distributed Computing, pages 453-460, 2006. URL: https://doi.org/10.1007/s00446-005-0127-6.
  25. Hiroaki Ookawa and Taisuke Izumi. Filling Logarithmic Gaps in Distributed Complexity for Global Problems. In Proccedings of 41st International Conference on Current Trends in Theory and Practice of Informatics (SOFSEM), pages 377-388, 2015. URL: https://doi.org/10.1007/978-3-662-46078-8_31.
  26. Madhumangal Pal. Intersection Graphs: An Introduction. arXiv, 2014. URL: http://arxiv.org/abs/1404.5468.
  27. 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), pages 743-756, 2017. URL: https://doi.org/10.1145/3055399.3055449.
  28. Gopal Pandurangan, Peter Robinson, and Michele Scquizzato. The Distributed Minimum Spanning Tree Problem. Bulletin of the European Association for Theoretical Computer Science (EATCS), 2018. URL: http://eatcs.org/beatcs/index.php/beatcs/article/view/538.
  29. David Peleg and Vitaly Rubinovich. A Near-Tight Lower Bound on the Time Complexity of Distributed Minimum-Weight Spanning Tree Construction. SIAM Journal on Computing, pages 1427-1442, 2000. URL: https://doi.org/10.1137/S0097539700369740.
  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. In Proceedings of the 43th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 363-372, 2011. URL: https://doi.org/10.1145/1993636.1993686.
  31. Mark N. Wegman and Larry Carter. New Hash Functions and Their Use in Authentication and Set Equality. Journal of Computer and System Sciences, pages 265-279, 1981. URL: https://doi.org/10.1016/0022-0000(81)90033-7.
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 About DROPS Imprint Privacy Contact