Low-Congestion Shortcuts for Graphs Excluding Dense Minors
share
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 Õ(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 Õ(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 Θ̃(D)-round distributed algorithms for many fundamental communication primitives and optimization problems including minimum spanning tree, minimum cut, and shortest-path approximations.
READ FULL TEXT