arXiv preprint ·
Almost-Linear Decremental Single-Source Distance Estimates in Directed Graphs via Cut Balance
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
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(Δ)+(N+Δ_{\mathrm{eff}}+\mathcal{L}/\varepsilon)S^{o(1)}$ time, where $Δ$ counts raw updates, $Δ_{\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(Δ)+(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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Fast mixing of the SYK model at high temperatures
Explicit Asymptotic Bounds for Sequential Calibration Beyond $T^{2/3}$
Near-Exact Computation of Independent Chip Model Placement Probabilities for Thousands of Players
How to Fix a Broken Metric: A Linear Kernel, Tight Bounds, and Tree Metrics
Improved Sublinear Algorithms for Maximal Independent Set and Metric Steiner Forest
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.