Space-Optimal Algorithms for Spanning Forests in Dynamic Streams at Every Confidence Level: With and Without Deletion Constraints

arXiv:2611.04365 · cs.DS, cs.CC · Submitted 2026-11-03 · Read on arXiv

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

Related papers