2020/08/07 by Mohsen Ghaffari, Bernhard Haeupler, Ghaffari, Mohsen +1 · 1 citation
Computer Science · Mathematics · #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #FOS: Mathematics #Parallel #and Cluster Computing (cs.DC) #cs.DC #cs.DS #math.CO
paper · pdf · doi:10.48550/arxiv.2008.03091
arxiv created 2020/08/07 · arxiv updated 2020/08/10
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, elementary, and constructive - featuring a Θ(δD)-round distributed construction algorithm. Our results are tight up to O(1) 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 O(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 that many graph families, including any minor-excluded ones, have near-optimal Θ(D)-round distributed algorithms for many fundamental communication primitives and optimization problems including minimum spanning tree, minimum cut, and shortest-path approximations.