Metraipolis › archive › dc_bde04b1ff137
Reachability Diameter: Beyond the Square-Root Barrier, with Polynomial Hardness — arXiv:2611.05712
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.05712
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-05T18:31:31.295Z
- SHA-256 of the archived text
ea8876ec8e1dd803157c6d7fcc223719328905f69c7fbceb696004358d6f8083- Stable URL of this page
https://metraipolis.com/documento/dc_bde04b1ff137
How to cite
Reachability Diameter: Beyond the Square-Root Barrier, with Polynomial Hardness — arXiv:2611.05712 — arXiv (en), https://arxiv.org/abs/2611.05712 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_bde04b1ff137 (Metraipolis archive dc_bde04b1ff137, sha256 ea8876ec8e1dd803157c6d7fcc223719328905f69c7fbceb696004358d6f8083)
BibTeX
@misc{dcbde04b1ff137,
title = {Reachability Diameter: Beyond the Square-Root Barrier, with Polynomial Hardness — arXiv:2611.05712},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.05712},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_bde04b1ff137; sha256 ea8876ec8e1dd803157c6d7fcc223719328905f69c7fbceb696004358d6f8083},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.05712. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
The reachability diameter of a directed graph is the maximum finite shortest-path distance across all pairs of vertices. It has received recent attention under this name, although the underlying quantity has long played a central role in shortcut set and parallel reachability. Notably, Bals et al. establish hardness for every polynomial-factor approximation in nearly-linear time for weighted digraphs. Yet they give $n^{1/2+o(1)}$-approximation in the unweighted regime with nearly-linear running time, and their conditional lower bounds rule out certain constants only, leaving open whether polynomial loss is necessary. We give a randomized algorithm that estimates the reachability diameter of an unweighted digraph within a factor $n^{1/3+o(1)}$, with high probability, in $\widetilde{O}(m+n)$ time. We complement our algorithm with a lower bound conditional on the 3-uniform Hyperclique hypothesis, ruling out an $n^{2/15-\varepsilon}$-approximation in $\widetilde{O}(m+n)$ time for every fixed $\varepsilon\in(0,2/15)$, establishing the necessity of polynomial loss for nearly-linear time algorithms.
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.05712 — 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-05T18:21:04.022Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).