Metraipolis › archive › dc_ac4e73073d8f

Almost-Linear Decremental Single-Source Distance Estimates in Directed Graphs via Cut Balance — arXiv:2610.07468

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.07468
License (as archived)
CC0-1.0
Archived
2026-10-07T13:40:32.025Z
SHA-256 of the archived text
3fa3c8b1effeca4607b4cae424b63bfd33bb1eda15c65063efc0e5ba273ff9b5
Stable URL of this page
https://metraipolis.com/documento/dc_ac4e73073d8f

How to cite

Almost-Linear Decremental Single-Source Distance Estimates in Directed Graphs via Cut Balance — arXiv:2610.07468 — arXiv (en), https://arxiv.org/abs/2610.07468 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_ac4e73073d8f (Metraipolis archive dc_ac4e73073d8f, sha256 3fa3c8b1effeca4607b4cae424b63bfd33bb1eda15c65063efc0e5ba273ff9b5)
BibTeX
@misc{dcac4e73073d8f,
  title = {Almost-Linear Decremental Single-Source Distance Estimates in Directed Graphs via Cut Balance — arXiv:2610.07468},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.07468},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_ac4e73073d8f; sha256 3fa3c8b1effeca4607b4cae424b63bfd33bb1eda15c65063efc0e5ba273ff9b5},
  year = {2026}
}

Archived text

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

We give a deterministic reduction for maintaining simultaneous approximate single-source distance estimates in online decremental directed graphs. For positive integer weights in $[1,W]$, the algorithm maintains an explicit array of integer $(1+\varepsilon)$ upper estimates, identifies unreachable vertices exactly, and answers numerical queries in constant time. Let $N=m+n$, $S=N+\lceil1/\varepsilon\rceil$, and assume $\log W=\operatorname{polylog}(S)$. Initialization and all updates take $O(\Delta)+(N+\Delta_{\mathrm{eff}}+\mathcal{L}/\varepsilon)S^{o(1)}$ time, where $\Delta$ counts raw updates, $\Delta_{\mathrm{eff}}=O(m(1+\log W)/\varepsilon)$ counts filtered updates, and $\mathcal{L}$ measures finite distance growth weighted by the current indegrees of the reachable subgraph. Removed edges and vertices that become unreachable incur no subsequent growth charge. Consequently, the worst-case bound is $O(\Delta)+(N/\varepsilon)S^{o(1)}$, which is almost linear for subpolynomial inverse accuracy. The reduction uses the dynamic minimum-ratio cut and exact reachability algorithms of van den Brand et al. (FOCS 2024). A degree-weighted clipped logarithmic potential turns constant relative cut balance into accuracy at every target; a successor cut then restores strict feasibility. A distance warm start and the energy released by decreasing return coefficients yield the refined growth bound. Return mass also amplifies the accuracy of the existing change detector. The public estimates can be monotone, with $O(n+\mathcal{J}/\varepsilon)$ array writes for an unweighted finite-growth measure $\mathcal{J}\le\mathcal{L}$. Execution uses rational arithmetic. A separate reduction extends the worst-case guarantee to nonnegative integer weights. The algorithm maintains numerical estimates and does not provide fast path reporting.

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/2610.07468 — 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-10-07T13:13:03.913Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).