Metraipolis › archive › dc_56ecacb60783
A Simple Subquadratic Cut Query Protocol for Directed Reachability — arXiv:2611.06906
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.06906
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-05T18:31:44.944Z
- SHA-256 of the archived text
0899e56f93fe9c0640ead9f439977edda67bb32bfb10ee4d0f0b83065f6f92b3- Stable URL of this page
https://metraipolis.com/documento/dc_56ecacb60783
How to cite
A Simple Subquadratic Cut Query Protocol for Directed Reachability — arXiv:2611.06906 — arXiv (en), https://arxiv.org/abs/2611.06906 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_56ecacb60783 (Metraipolis archive dc_56ecacb60783, sha256 0899e56f93fe9c0640ead9f439977edda67bb32bfb10ee4d0f0b83065f6f92b3)
BibTeX
@misc{dc56ecacb60783,
title = {A Simple Subquadratic Cut Query Protocol for Directed Reachability — arXiv:2611.06906},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.06906},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_56ecacb60783; sha256 0899e56f93fe9c0640ead9f439977edda67bb32bfb10ee4d0f0b83065f6f92b3},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.06906. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study $s$--$t$ reachability in an unweighted directed graph on $n$ vertices, accessed through a directed cut oracle: given $S\subseteq V$, the oracle returns the number of edges directed from $S$ to $V\setminus S$. Directed cut functions are submodular, and reachability asks whether the minimum $s$--$t$ cut has positive value. This connects the problem to the query complexity of submodular function minimisation. Whether or not reachability can be solved in truly subquadratic query complexity has been an outstanding open question for a decade. We give a simple algorithmic blueprint with two randomised implementations. The first uses $\widetilde O(n^{9/5})$ outgoing-cut queries; the second improves this bound to $\widetilde O(n^{5/3})$. The common idea is to construct an alternative orientation with the same underlying undirected graph and vertex-wise degree imbalances, thereby preserving reachability. We first approximate the target imbalances using an averaging and rounding procedure, then correct the remaining error with a flow. An earlier manuscript, made available in August 2026 in an online AI repository, reports an $\widetilde O(n^{3/2})$ query bound. Our contribution is a simple and comprehensible alternative approach that already achieves a polynomial saving over quadratic query complexity.
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.06906 — 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.033Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).