research-article

Public Access

Low-Congestion Shortcuts for Graphs Excluding Dense Minors

Authors:

Mohsen Ghaffari,

Bernhard HaeuplerAuthors Info & Claims

PODC'21: Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing

Pages 213 - 221

https://doi.org/10.1145/3465084.3467935

Published: 23 July 2021 Publication History

Abstract

We prove that any n-node graph G with diameter D admits shortcuts with congestion O(δ D log n) and dilation O(δ D), where δ is the maximum edge-density of any minor of G. Our proof is simple and constructive with a tildeΘ (δ D)-round1 distributed construction algorithm. Our results are tight up to logarithmic factors and generalize, simplify, unify, and strengthen several prior results. For example, for graphs excluding a fixed minor, i.e., graphs with constant δ, only a Õ (D2) bound was known based on a very technical proof that relies on the Robertson-Seymour Graph Structure Theorem.

A direct consequence of our result is this: many graph families, including any minor-excluded ones, have near-optimal tildeΘ(D)-round distributed algorithms for many fundamental communication primitives and optimization problems in the standard synchronous message-passing model with logarithmic message sizes, i.e., the CONGEST model. These problems include minimum spanning tree, minimum cut approximation, and shortest-path approximations.

Supplementary Material

MP4 File (PODC21-fp312.mp4)

Video Presentation of PODC'21 Paper: Low-Congestion Shortcuts for Graphs Excluding Dense Minors (Bernhard Haeupler - joint work with Mohsen Ghaffari)

Download
30.34 MB

References

[1]

Noga Alon, Paul Seymour, and Robin Thomas. 1990. A separator theorem for nonplanar graphs. Journal of the American Mathematical Society, Vol. 3, 4 (1990), 801--808.

[2]

Michal Dory and Mohsen Ghaffari. 2019. Improved distributed approximations for minimum-weight two-edge-connected spanning subgraph. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (PODC). 521--530.

Digital Library

[3]

Michael Elkin. 2004. Unconditional Lower Bounds on the Time-approximation Tradeoffs for the Distributed Minimum Spanning Tree Problem. In Proc. of the Symp. on Theory of Comp. (STOC). 331--340.

Digital Library

[4]

J.A. Garay, S. Kutten, and D. Peleg. 1993. A sub-linear time distributed algorithm for minimum-weight spanning trees. In Proc. of the Symp. on Found. of Comp. Sci. (FOCS).

[5]

Mohsen Ghaffari. 2015. Near-Optimal Scheduling of Distributed Algorithms. In the Proc. of the Int'l Symp. on Princ. of Dist. Comp. (PODC). to appear.

[6]

Mohsen Ghaffari and Bernhard Haeupler. 2016a. Distributed Algorithms for Planar Networks I: Planar Embedding. In the Proc. of the Int'l Symp. on Princ. of Dist. Comp. (PODC).

Digital Library

[7]

Mohsen Ghaffari and Bernhard Haeupler. 2016b. Distributed Algorithms for Planar Networks II: Low-Congestion Shortcuts, MST, and Min-Cut. In Pro. of ACM-SIAM Symp. on Disc. Alg. (SODA).

[8]

Mohsen Ghaffari, Fabian Kuhn, and Hsin-Hao Su. 2017. Distributed MST and routing in almost mixing time. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC). 131--140.

Digital Library

[9]

Mohsen Ghaffari and Jason Li. 2018. New Distributed Algorithms in Almost Mixing Time via Transformations from Parallel Algorithms. In 32nd International Symposium on Distributed Computing (DISC). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.

[10]

Mohsen Ghaffari and Merav Parter. 2017. Near-optimal distributed DFS in planar graphs. In 31st International Symposium on Distributed Computing (DISC). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.

[11]

John R Gilbert, Joan P Hutchinson, and Robert Endre Tarjan. 1984. A separator theorem for graphs of bounded genus. Journal of Algorithms, Vol. 5, 3 (1984), 391--407.

Digital Library

[12]

Bernhard Haeupler, D Ellis Hershkowitz, and David Wajc. 2018a. Round-and message-optimal distributed graph algorithms. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing. 119--128.

Digital Library

[13]

Bernhard Haeupler, D Ellis Hershkowitz, and David Wajc. 2019. Near-Optimal Schedules for Simultaneous Multicasts. arXiv cs.DS 2001.00072 (2019).

[14]

Bernhard Haeupler, Taisuke Izumi, and Goran Zuzic. 2016a. Low-congestion shortcuts without embedding. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing (PODC). 451--460.

Digital Library

[15]

Bernhard Haeupler, Taisuke Izumi, and Goran Zuzic. 2016b. Near-optimal low-congestion shortcuts on bounded parameter graphs. In International Symposium on Distributed Computing (DISC). Springer, 158--172.

[16]

Bernhard Haeupler and Jason Li. 2018. Faster Distributed Shortest Path Approximations via Shortcuts. In 32nd International Symposium on Distributed Computing (DISC). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.

[17]

Bernhard Haeupler, Jason Li, and Goran Zuzic. 2018b. Minor excluded network families admit fast distributed algorithms. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing (PODC). 465--474.

Digital Library

[18]

Naoki Kitamura, Hirotaka Kitagawa, Yota Otachi, and Taisuke Izumi. 2019. Low-Congestion Shortcut and Graph Parameters. In 33rd International Symposium on Distributed Computing (DISC). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.

[19]

Shay Kutten and David Peleg. 1995. Fast Distributed Construction of K-dominating Sets and Applications. In the Proc. of the Int'l Symp. on Princ. of Dist. Comp. (PODC). 238--251.

[20]

Frank Thomson Leighton, Bruce M Maggs, and Satish B Rao. 1994. Packet routing and job-shop scheduling ino (congestion dilation) steps. Combinatorica, Vol. 14, 2 (1994), 167--186.

[21]

Jason Li and Merav Parter. 2019. Planar diameter via metric compression. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC). 152--163.

Digital Library

[22]

Richard J Lipton and Kenneth W Regan. 2013. People, Problems, and Proofs: Essays from Gödel's Lost Letter: 2010 .Springer Science & Business Media.

[23]

Richard J Lipton and Robert Endre Tarjan. 1979. A separator theorem for planar graphs. SIAM J. Appl. Math., Vol. 36, 2 (1979), 177--189.

Digital Library

[24]

Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. 2020. Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths. In Treewidth, Kernels, and Algorithms. Springer, 112--128.

[25]

Zvi Lotker, Boaz Patt-Shamir, and David Peleg. 2006. Distributed MST for constant diameter graphs. Distributed Computing, Vol. 18, 6 (2006), 453--460.

Digital Library

[26]

Gary L Miller. 1984. Finding small simple cycle separators for 2-connected planar graphs. In Proceedings of the sixteenth annual ACM symposium on Theory of computing (STOC). ACM, 376--382.

Digital Library

[27]

Jaroslav Nevs etvr il and Patrice Ossona De Mendez. 2012. Sparsity: graphs, structures, and algorithms. Vol. 28. Springer Science & Business Media.

[28]

Jaroslav Nevs etvr il, Eva Milková, and Helena Nevs etvr ilová. 2001. Otakar Boruvka on minimum spanning tree problem translation of both the 1926 papers, comments, history. Discrete Math., Vol. 233, 1 (2001), 3--36.

Digital Library

[29]

David Peleg. 2000. Distributed Computing: A Locality-sensitive Approach. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA.

[30]

David Peleg and Vitaly Rubinovich. 1999. A Near-Tight Lower Bound on the Time Complexity of Distributed MST Construction. In Proc. of the Symp. on Found. of Comp. Sci. (FOCS). 253--.

[31]

Neil Robertson and Paul D. Seymour. 1986. Graph minors. II. Algorithmic aspects of tree-width. Journal of algorithms, Vol. 7, 3 (1986), 309--322.

[32]

Neil Robertson and Paul D Seymour. 2003. Graph minors. XVI. Excluding a non-planar graph. Journal of Combinatorial Theory, Series B, Vol. 89, 1 (2003), 43--76.

Digital Library

[33]

Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Pandurangan, David Peleg, and Roger Wattenhofer. 2012. Distributed verification and hardness of distributed approximation. SIAM J. Comput., Vol. 41, 5 (2012), 1235--1265.

Digital Library

[34]

Andrew Thomason. 2001. The extremal function for complete minors. Journal of Combinatorial Theory, Series B, Vol. 81, 2 (2001), 318--338.

Digital Library

Cited By

Chandra SChang YDory MGhaffari MLeitersdorf DAgrawal KPetrank E(2024)Fast Broadcast in Highly Connected NetworksProceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3626183.3659959(331-343)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3626183.3659959
Bousquet NFeuilloley LPierron T(2024)Local certification of graph decompositions and applications to minor-free classesJournal of Parallel and Distributed Computing10.1016/j.jpdc.2024.104954193:COnline publication date: 1-Nov-2024
https://dl.acm.org/doi/10.1016/j.jpdc.2024.104954
Parter M(2023)Secure Computation Meets Distributed Universal Optimality2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00144(2336-2368)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00144
Show More Cited By

Index Terms

Low-Congestion Shortcuts for Graphs Excluding Dense Minors
1. Theory of computation
  1. Design and analysis of algorithms
    1. Distributed algorithms

Recommendations

Low-Congestion Shortcuts in Constant Diameter Graphs
PODC'21: Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing

Low congestion shortcuts, introduced by Ghaffari and Haeupler (SODA 2016), provide a unified framework for global optimization problems in the CONGEST model of distributed computing. Roughly speaking, for a given graph G and a collection of vertex-...
Low-Congestion Shortcuts without Embedding
PODC '16: Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing

Distributed optimization algorithms are frequently faced with solving sub-problems on disjoint connected parts of a network. Unfortunately, the diameter of these parts can be significantly larger than the diameter of the underlying network, leading to ...
A Simple Deterministic Distributed MST Algorithm with Near-Optimal Time and Message Complexities

The distributed minimum spanning tree (MST) problem is one of the most central and fundamental problems in distributed graph algorithms. Kutten and Peleg devised an algorithm with running time O(D + √n ⋅ log^* n), where D is the hop diameter of the input ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PODC'21: Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing

July 2021

590 pages

ISBN:9781450385480

DOI:10.1145/3465084

General Chair:
Avery Miller
University of Manitoba, Canada
,
Program Chair:
Keren Censor-Hillel
Technion, Israel

Copyright © 2021 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 July 2021

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Science Foundation
Swiss National Science Foundation
European Research Council

Conference

PODC '21

Sponsor:

PODC '21: ACM Symposium on Principles of Distributed Computing

July 26 - 30, 2021

Virtual Event, Italy

Acceptance Rates

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
173
Total Downloads

Downloads (Last 12 months)59
Downloads (Last 6 weeks)10

Reflects downloads up to 29 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Chandra SChang YDory MGhaffari MLeitersdorf DAgrawal KPetrank E(2024)Fast Broadcast in Highly Connected NetworksProceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3626183.3659959(331-343)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3626183.3659959
Bousquet NFeuilloley LPierron T(2024)Local certification of graph decompositions and applications to minor-free classesJournal of Parallel and Distributed Computing10.1016/j.jpdc.2024.104954193:COnline publication date: 1-Nov-2024
https://dl.acm.org/doi/10.1016/j.jpdc.2024.104954
Parter M(2023)Secure Computation Meets Distributed Universal Optimality2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00144(2336-2368)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00144
Anagnostides ILenzen CHaeupler BZuzic GGouleakis T(2023)Almost universally optimal distributed Laplacian solvers via low-congestion shortcutsDistributed Computing10.1007/s00446-023-00454-036:4(475-499)Online publication date: 31-Jul-2023
https://dl.acm.org/doi/10.1007/s00446-023-00454-0

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents