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

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