Simple shortest-path trees give good low-stretch spanning trees
Low-Stretch Spanning Trees via Smoothed Analysis of Dijkstra's Algorithm
Data Structures and Algorithms
Summary
Finding a tree inside a network that keeps distances roughly the same is usually complicated. The authors explain why simply picking any starting point and running a shortest-path algorithm like Dijkstra’s often works well in practice. They show that if you slightly adjust the network's edge weights, this simple method reliably finds a good approximation. Their approach also gives a new way to efficiently compute such trees.
What this means in practice
- •For network engineers: Generate reliable approximate shortest-path trees for large weighted networks more simply and efficiently.
- •For distributed systems developers: Design communication backbones with provable distance guarantees based on simple shortest-path computations.
Authors
Ioannis Dorkofikis, Bernhard Haeupler, Maximilian Probst Gutenberg, Antti Roeyskoe, Aurelio Sulser, Gernot Zöcklein
Abstract
Given an undirected weighted graph $G$, a $γ$-approximate low-stretch spanning tree (LSST) $T \subseteq G$ is a tree that approximates the distance metric of $G$ up to a $γ$-factor in expectation. Currently, existing algorithms to find a provably good LSST carefully construct an approximate shortest-path tree from an arbitrary source. The resulting algorithms are intricate. In contrast, practitioners observed that a much simpler heuristic performs surprisingly well: choose an arbitrary root, run Dijkstra's algorithm, and use the resulting shortest-path tree as an LSST. In this paper, we give a smoothed analysis of shortest-path tree algorithms, such as Dijkstra's algorithm, that explains this behavior. We show that adding a small perturbation to the weights of the input graph suffices to turn the shortest path tree rooted at an arbitrary node in the resulting graph into an $\tilde{O}(1)$-approximate LSST. We further show that the set of perturbations can be computed efficiently from few low-diameter decompositions (LDDs). Thus, our proof is also constructive in the sense of giving a novel approach to computing LSSTs.