In a graph $G = (V, E)$ with $n = |V|$ nodes and $m = |E|$ edges, the $t$-Pairs Shortest Paths problem, introduced by Cohen, aims to approximate the distances between $t$ prespecified pairs of vertices. Recently, this problem has garnered renewed attention, especially for cases where $t = \Theta(n)$: the $n$-Pairs Shortest Paths problem. New algorithms and conditional lower bounds have been developed by Dalirrooyfard, Jin, Vassilevska Williams, and Wein, as well as Chechik, Hoch, and Lifshitz.
This paper presents the first algorithm for the $n$-Pairs Shortest Paths problem in weighted undirected graphs that achieves a $(2 - \alpha)k$-approximation, with a constant $\alpha > 0$, running in $\tilde{O}(mn^{1/k} + n^{1 + 2/k})$ time. Specifically, we introduce a $1.622k$-approximation, improving upon the $(2k - 3)$-approximation of Chechik, Hoch, and Lifshitz for non-super sparse graphs, thus answering an open question posed by them. We also develop improved approximation algorithms for unweighted graphs and dense weighted graphs that surpass the results of Dalirrooyfard et al. and Chechik, Hoch, and Lifshitz.
Our main technical contribution is the new heavy-edge technique. Using this technique, we transform an algorithm with an approximation guarantee depending on $W_{uv}$, the weight of the heaviest edge on the shortest path between $u$ and $v$, into an algorithm with a purely multiplicative approximation that does not depend on $W_{uv}$.
Blogger's Review: This paper makes significant strides in the $n$-Pairs Shortest Paths problem for weighted undirected graphs, particularly with the introduction of the heavy-edge technique, which enhances algorithm performance. This novel approach offers a fresh perspective on graph algorithms, warranting further exploration of its potential applications in other graph algorithm contexts.