paper

Additive, Near-Additive, and Multiplicative Approximations for APSP in Weighted Undirected Graphs: Trade-offs and Algorithms

arXiv:2509.04640

Abstract

We present a $+ 2 \sum_{i = 1}^{k + 1} W_{i}$ -APASP algorithm for dense weighted graphs with runtime $O ~ (n^{2 + \frac{1}{3 k + 2}})$ , where $W_{i}$ is the weight of an $i^{t h}$ heaviest edge on a shortest path. Dor, Halperin and Zwick [FOCS'96, SICOMP'00] had two algorithms for the commensurate unweighted $+ 2 \cdot (k + 1)$ -APASP: $O ~ (n^{2 - \frac{1}{k + 2}} m^{\frac{1}{k + 2}})$ runtime for sparse graphs and $O ~ (n^{2 + \frac{1}{3 k + 2}})$ runtime for dense graphs. Cohen and Zwick [SODA'97, JALG'01] adapted the sparse variant to weighted graphs: $+ 2 \sum_{i = 1}^{k + 1} W_{i}$ -APASP algorithm in the same runtime. We show an algorithm for dense weighted graphs. For nearly additive APASP, we present a $(1 + ε, min {2 W_{1}, 4 W_{2}})$ -APASP algorithm with $O ~ ((\frac{1}{ε})^{O (1)} \cdot n^{2.15135313} \cdot lo g W)$ runtime. This improves the $(1 + ε, 2 W_{1})$ -APASP of Saha and Ye [SODA'24]. For multiplicative APASP, we show a framework of $(\frac{3 ℓ + 4}{ℓ + 2} + ε)$ -APASP algorithms, reducing the runtime of Akav and Roditty [ESA'21] for dense graphs and generalizing the $(2 + ε)$ -APASP algorithm of Dory et al [SODA'24]. Our base case is a $(\frac{7}{3} + ε)$ -APASP in $O ~ ((\frac{1}{ε})^{O (1)} \cdot n^{2.15135313} \cdot lo g W)$ runtime, improving the $\frac{7}{3}$ -APASP algorithm of Baswana and Kavitha [FOCS'06, SICOMP'10] for dense graphs. Finally, we "bypass" an $I^~ c ◯ (n^{I ¨} )$ conditional lower bound by Dor, Halperin, and Zwick for $I^\pm$ -APASP with $I^\pm < 2$ , by allowing an additive term (e.g. $(\frac{6 k + 3}{3 k + 2}, \sum_{i = 1}^{k + 1} W_{i})$ -APASP in $O ~ (n^{2 + \frac{1}{3 k + 2}})$ runtime).