Low-Congestion Shortcuts for Graphs Excluding Dense Minors

DOI10.1145/3465084.3467935arXiv2008.03091OpenAlexW3187061951MaRDI QIDQ6201952FDOQ6201952

Authors: Mohsen Ghaffari, Bernhard Haeupler 

Publication date: 26 March 2024

Published in: Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Abstract: We prove that any $n$-node graph $G$ with diameter $D$ admits shortcuts with congestion $O(deltaDlogn)$ and dilation $O(deltaD)$, where $delta$ is the maximum edge-density of any minor of $G$. Our proof is simple, elementary, and constructive - featuring a $ildeTheta(deltaD)$-round distributed construction algorithm. Our results are tight up to $ildeO(1)$ factors and generalize, simplify, unify, and strengthen several prior results. For example, for graphs excluding a fixed minor, i.e., graphs with constant $delta$, only a $ildeO(D^2)$ 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 that many graph families, including any minor-excluded ones, have near-optimal $ildeTheta(D)$-round distributed algorithms for many fundamental communication primitives and optimization problems including minimum spanning tree, minimum cut, and shortest-path approximations.

Full work available at URL: https://arxiv.org/abs/2008.03091

zbMATH Keywords

minimum spanning treedilationcongestionplanar graphsdistributed graph algorithmslow-congestion shortcutsminor-exluded graphs

Mathematics Subject Classification ID

Distributed algorithms (68W15) Distributed systems (68M14)

This page was built for publication: Low-Congestion Shortcuts for Graphs Excluding Dense Minors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6201952)