Metraipolis › archive › dc_42eef9c1ba53

Roundtrip All-Pairs Shortest Paths in Directed Graphs — arXiv:2611.05311

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.05311
License (as archived)
CC0-1.0
Archived
2026-11-04T12:59:28.941Z
SHA-256 of the archived text
2a9556ad306de476adb8be547ce434401319e8738b9e978af30b19a1d5182cb4
Stable URL of this page
https://metraipolis.com/documento/dc_42eef9c1ba53

How to cite

Roundtrip All-Pairs Shortest Paths in Directed Graphs — arXiv:2611.05311 — arXiv (en), https://arxiv.org/abs/2611.05311 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_42eef9c1ba53 (Metraipolis archive dc_42eef9c1ba53, sha256 2a9556ad306de476adb8be547ce434401319e8738b9e978af30b19a1d5182cb4)
BibTeX
@misc{dc42eef9c1ba53,
  title = {Roundtrip All-Pairs Shortest Paths in Directed Graphs — arXiv:2611.05311},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.05311},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_42eef9c1ba53; sha256 2a9556ad306de476adb8be547ce434401319e8738b9e978af30b19a1d5182cb4},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.05311. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2611.05311 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-04T12:35:02.338Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).