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 $δ$. Nelson and Yu proved an $Ω(v\log^2v\log(v/δ))$-bit lower bound, establishing the AGM algorithm's optimality for each fixed $0<ε<1$ and $2^{-v^{1-ε}}<δ\le1/4$. We resolve the remaining high-confidence regime: for every $0<δ\le1/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 $Θ((\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\ge0$ is given in advance. Total deletions, restorations, and intermediate absence counts are unrestricted. For a single report and every $0<δ\le1/4$, matching lower bounds and a one-pass randomized algorithm yield optimal space $Θ(\mathcal L(v,Z,\log(1/δ)))$ 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.

The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.

More in Data Structures & Algorithms

• arXiv preprint · 3 November 2026

  Semidirect sums of tensors and the matrix multiplication exponent

  Baitian Li
• arXiv preprint · 4 November 2026

  Towards the Query Complexity of Sampling under Strong Log-Concavity and Log-Sobolev Inequalities

  Huanjian Zhou and Taiji Suzuki
• arXiv preprint · 3 November 2026

  State Evolution and Universality of Iterated Linear Programs for the Binary Perceptron

  Jianan Zhang and Shuangping Li
• arXiv preprint · 4 November 2026

  Softmax Attention with Any Temperature in Fixed Dimension: Matching the Best Known Maximum-Inner-Product Bounds

  Zixuan Huang and Guozhang Chen
• arXiv preprint · 4 November 2026

  An Engineering Reading of the Bounded Halting Problem and Observable Properties of a Universal Machine

  Sergey Salishev

All new papers in Data Structures & Algorithms