Algorithms improve weighted graph path approximations below previous runtime limits
Smallest Multiplicative Stretch for an $α$-APASP Below $\widetilde O \left(n^ω\right)$ Runtime
Data Structures and Algorithms
Summary
Finding the shortest paths in weighted networks is a common challenge, and many algorithms approximate these paths to save time. The authors developed new methods that improve how fast these approximations can be computed for certain accuracy levels, beating previous known time limits. They use advanced mathematical techniques related to matrix operations to achieve these speedups. This helps better understand the computational limits of approximating shortest paths in graphs.
What this means in practice
- •For graph algorithm engineers: Implement faster approximate shortest path computations on weighted networks with improved theoretical runtime guarantees.
- •For network optimization teams: Use improved approximation algorithms to speed up routing and planning tasks in large weighted networks while ensuring controlled path quality.
A theory result. No direct application yet.
Authors
Lakshay Saggi, Ariel Sapir
Abstract
Dor, Halperin and Zwick [FOCS'96; SICOMP'00] showed that $(2-\varepsilon)$-APASP is at least as hard as BMM for every fixed $0<\varepsilon<1$. Zwick [FOCS'98; JACM'02] gave a $2$-APASP algorithm in $\widetilde O(n^{ω+o(1)}\log W_{\max})$ runtime, where $W_{\max}$ is the maximum edge weight. Bringmann, K{ü}nnemann and W{ę}grzycki [STOC'19] removed this logarithmic factor. Using OpenAI's recent bound $ω\leq\frac{9}{4}$ gives $\widetilde O\left(n^{\frac{9}{4}+o(1)}\right)$ time. We present two weighted undirected $2$-APASP algorithms. The first uses $(\min,\max)$-products. Earlier rectangular FMM bounds of Vassilevska Williams, Yinzhan Xu, Zixuan Xu and Zhou [SODA'24] and Alman, Duan, Vassilevska Williams, Yinzhan Xu, Zixuan Xu and Zhou [SODA'25] give $\widetilde O(n^{2.36999465})$ runtime, below the previous $ω\leq2.371177$ of Dupont, Eisenberger, Kozlovskii, Mehrabian, Ruiz, See, Zhou, Alman, Vassilevska Williams and Balog [arXiv'26]. Current rectangular FMM bounds give $\widetilde O(n^{2.34549151})$, independent of $W_{\max}$. For integer weights, our second algorithm has $\widetilde O(n^{ω-\frac{(ω-2)^2}{ω-1}+o(1)}\log^{O(1)}W_{\max})$ runtime, with exponent below $ω$ whenever $ω>2$. The rectangular bounds of Uzna{ń}ski [arXiv'26] or of Amanov, van den Berg and Zuiddam [arXiv'26] give $\widetilde O(n^{2.17157288}\log^{O(1)}W_{\max})$.