# Low-Stretch Spanning Trees via Smoothed Analysis of Dijkstra's Algorithm

Preprint · Ioannis Dorkofikis, Bernhard Haeupler, Maximilian Probst Gutenberg, Antti Roeyskoe, Aurelio Sulser, Gernot Zöcklein

- Archive id: arxiv:2609.35136
- Published: 2026-09-28
- arXiv: https://arxiv.org/abs/2609.35136
- Source URL: https://arxiv.org/abs/2609.35136
- PDF: https://arxiv.org/pdf/2609.35136
- Provenance: arxiv

## 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.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.