2021/06/03 by Shimon Kogan, Kogan, Shimon, Merav Parter +1
Computer Science · #Complexity and Algorithms in Graphs #Cryptography and Data Security #Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Parallel #Stochastic Gradient Optimization Techniques #and Cluster Computing (cs.DC) #cs.DC #cs.DS
paper · pdf · doi:10.48550/arxiv.2106.01894
To appear in PODC 2021
openalex publication_date 2021/06/03 · arxiv created 2021/06/07 · arxiv updated 2021/06/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 S1,…, S_ℓ ⊆ V(G), (c,d) low-congestion shortcuts augment each subgraph G[Si] with a subgraph Hi ⊆ G such that: (i) each edge appears on at most c subgraphs (congestion bound), and (ii) the diameter of each subgraph G[Si] ∪ Hi 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=\widetildeΩ(n(D-2)/(2D-2)). A nearly matching upper bound, however, was only recently obtained for D ∈ \3,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+ε)-approximate minimum cuts and more.