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

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 Ω(vlog²vlog(v/δ))-bit lower bound, establishing the AGM algorithm's optimality for each fixed $0<ε<1$ and 2^-v1-ε<δ≤1/4. We resolve the remaining high-confidence regime: for every 0<δ≤1/4, matching lower bounds and an algorithm give \[ Θ\!(min\{v^2,\;vlog(v/δ)log^2\!(2+v/log(v/δ))\}) \] bits, improving space by up to a factor of Θ((log v/loglog v)²) 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≥0 is given in advance. Total deletions, restorations, and intermediate absence counts are unrestricted. For a single report and every 0<δ≤1/4, matching lower bounds and a one-pass randomized algorithm yield optimal space Θ( L(v,Z,log(1/δ))) bits, where xZ(t)=min+1,v,√vt\ and \[ L(v,Z,t)=vlog vmin\{log^2v,log^2(Z+2)\} +vtlog\!(1+{x_Z(t)}t)log\!(1+ v{x_Z(t)}). \] At zero error, a lower bound for all zero-error algorithms and a matching deterministic algorithm give optimal space \[ Θ\!(min\{v^2,v(Z+1)log(1+v/(Z+1))\}) \] bits. Together, these results characterize the memory required across all confidence levels and report-time edge-loss bounds.