Metraipolis › archive › dc_502b5103fa95
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-04T19:07:45.076Z
- SHA-256 of the archived text
41a1403d12a56c371211be39bb2b407b8c0f8ed59fef66645a2e97076551ce88- Stable URL of this page
https://metraipolis.com/documento/dc_502b5103fa95
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_502b5103fa95 (Metraipolis archive dc_502b5103fa95, sha256 41a1403d12a56c371211be39bb2b407b8c0f8ed59fef66645a2e97076551ce88)
BibTeX
@misc{dc502b5103fa95,
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_502b5103fa95; sha256 41a1403d12a56c371211be39bb2b407b8c0f8ed59fef66645a2e97076551ce88},
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-04T18:40:52.488Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).