Space-Optimal Algorithms for Spanning Forests in Dynamic Streams at Every Confidence Level: With and Without Deletion Constraints
cs.DS, cs.CC
Submitted: 2026-11-03
Updated: 2026-11-03
License: http://creativecommons.org/licenses/by/4.0/
The gist: We characterize the optimal space for one-pass spanning-forest computation in dynamic streams of v-vertex simple graphs with failure probability at most δ.
Abstract
We characterize the optimal space for one-pass spanning-forest computation in dynamic streams of v-vertex simple graphs with failure probability at most δ. Nelson and Yu proved an Ω(v 2v (v/δ)) -bit lower bound, establishing the AGM algorithm's optimality for each fixed 0<ε<1 and 2-v 1-ε<δ at most1/4. We resolve the remaining high-confidence regime: for every 0<δ at most1/4, matching lower bounds and an algorithm give Θ! (v squared,;v (v/δ) 2! (2+ v over(v/δ))) bits, improving space by up to a factor of Θ((v/ v) 2) in this regime. We also study streams with at most Z previously inserted edges deleted and not yet reinserted at report time, where the integer Z at least0 is given in advance. Total deletions, restorations, and intermediate absence counts are unrestricted. For a single report and every 0<δ at most1/4, matching lower bounds and a one-pass randomized algorithm yield optimal space Θ(L(v,Z, (1/δ))) bits, where x Z(t)= Z+1,v, sqrt vt and L(v,Z,t)=v v 2v, 2(Z+2) +vt ! (1+ t) ! (1+ v x Z(t)). At zero error, a lower bound for all zero-error algorithms and a matching deterministic algorithm give optimal space Θ! (v squared,v(Z+1) (1+v/(Z+1))) bits. Together, these results characterize the memory required across all confidence levels and report-time edge-loss bounds.
Sources
- An Asymptotically Optimal Algorithm for Maximum Matching in Dynamic Streams
- Optimal streaming and tracking distinct elements with high probability
- Tower of algebraic function fields with maximal Hasse-Witt invariant and tensor rank of multiplication in any extension of $\mathbb{F}_2$ and $\mathbb{F}_3$
- Efficient Document Exchange and Error Correcting Codes with Asymmetric Information
- Hybrid Sketching Methods for Dynamic Connectivity on Sparse Graphs
- Sketching Sparse Matrices
- Dynamic graph connectivity with improved worst case update time and sublinear space
- Streaming Algorithms for Connectivity Augmentation
- Data Streams with Bounded Deletions
- Fault-Tolerant Distance Oracles Below the $n \cdot f$ Barrier
- Optimal lower bounds for universal relation, and for samplers and finding duplicates in streams
- Near-optimal Hypergraph Sparsification in Insertion-only and Bounded-deletion Streams
- Optimal Lower Bounds for Distributed and Streaming Spanning Forest Computation
- Exploring the Landscape of Distributed Graph Sketching
- Random Order in Quantum Streaming: Replenishment and Robust Lower Bounds
Related papers
- Exploiting Low Scanwidth to Resolve Soft Polytomies
- PHastR: Faster Minimal Perfect Hashing with Rotated Layouts
- Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Equivalence with k-SUM in 2D
- Polynomial-time computation of p-contraction fixed points for even p
- Separations Between Submodular-Like Graph Widths
- Bounded Integer Programming in Almost N 2d Time