Low-Congestion Shortcuts in Constant Diameter Graphs

DOI10.1145/3465084.3467927arXiv2106.01894OpenAlexW3185869381MaRDI QIDQ6201951FDOQ6201951

Authors: Shimon Kogan, M. Parter 

Publication date: 26 March 2024

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

Abstract: 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-disjoint connected subsets $S_1,ldots,S_{e}llsubseteqV(G)$, $(c,d)$ low-congestion shortcuts augment each subgraph $G[S_i]$ with a subgraph $H_{i}subseteqG$ such that: (i) each edge appears on at most $c$ subgraphs (congestion bound), and (ii) the diameter of each subgraph $G[S_i]cup{H}_i$ is bounded by $d$ (dilation bound). It is desirable to compute shortcuts of small congestion and dilation as these quantities capture the round complexity of many global optimization problems in the congest model. For $n$-vertex graphs with constant diameter $D=O(1)$, Elkin (STOC 2004) presented an (implicit) shortcuts lower bound with $c+d=widetildeOmega(n^{(D-2)/(2D-2)})$. A nearly matching upper bound, however, was only recently obtained for $Din3,4$ by Kitamura et al. (DISC 2019). In this work, we resolve the long-standing complexity gap of shortcuts in constant diameter graphs, originally posed by Lotker et al. (PODC 2001). We present new shortcut constructions which match, up to poly-logarithmic terms, the lower bounds of Das-Sarma et al. As a result, we provide improved and existentially optimal algorithms for several network optimization tasks in constant diameter graphs, including MST, $(1+epsilon)$-approximate minimum cuts and more.

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

zbMATH Keywords

shortcutscongest modelglobal network optimization

Mathematics Subject Classification ID

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

This page was built for publication: Low-Congestion Shortcuts in Constant Diameter Graphs

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