Roundtrip shortest path approximation advances speed and accuracy in directed graphs
Roundtrip All-Pairs Shortest Paths in Directed Graphs
Data Structures and Algorithms
Summary
Finding the shortest roundtrip paths between all points in a directed network is challenging because some points can't be reached from others. The authors study a special metric called roundtrip distance, measuring the cost to go from one point to another and back, which is more manageable. They present new algorithms that can quickly estimate these roundtrip distances within a factor of 3, and show that improving on this factor is very hard. Their results offer both faster methods and limits on how well these distances can be approximated.
What this means in practice
- •For network routing engineers: Calculate fast approximations of roundtrip distances in directed networks to improve routing and path selection.
- •For graph algorithm developers: Develop efficient tools for approximate distance queries in large directed graphs using new tradeoffs between accuracy and speed.
Authors
Shiri Chechik, Gur Lifshitz
Abstract
We study approximation algorithms for All-Pairs Shortest Paths (APSP) in directed graphs under the roundtrip metric. In directed graphs, even finite-factor approximation of ordinary one-way distances must distinguish reachable from unreachable vertex pairs, and therefore computes transitive closure, a problem equivalent to Boolean matrix multiplication (BMM) under standard reductions. The roundtrip distance, defined as $\text{dist}_G(u \leftrightarrows v) = \text{dist}_G(u \to v) + \text{dist}_G(v \to u)$, offers a natural and robust relaxation. It measures the cost of traveling from $u$ to $v$ and back, satisfies the triangle inequality, and is inherently symmetric. While this metric has become central to the study of directed roundtrip spanners and compact routing, the fundamental problem of all-pairs roundtrip distance approximation has remained largely unexplored. In this work, we present a comprehensive study of roundtrip APSP and distance oracles, presenting several new lower and upper bounds. On the algorithmic side, our main result is a combinatorial algorithm that computes a stretch-$3$ approximation to all-pairs roundtrip distances in $\widetilde{O}(n^2 + \min\{m\sqrt{n},\, m^{1/3}n^{5/3}\})$ time. For edge weights in $[1,W]$, we also obtain a $(3+\varepsilon)$-approximation in $\widetilde O((n^{2.037}+nm^{2/3})\log(nW)/\varepsilon)$ time and a $(4+\varepsilon)$-approximation in $\widetilde O(n^{2.032}\log(nW)/\varepsilon)$ time using fast matrix multiplication. On the hardness side, we show that any stretch below $3$ would imply a breakthrough for BMM. We also obtain additional tradeoffs between stretch and running time.