A (Very) Nearly Optimal Sketch for $k$-Edge Connectivity Certificates
Authors:
Preprint
Abstract
In this note, we present a simple algorithm for computing a \emph{$k$-connectivity certificate} in dynamic graph streams. Our algorithm uses $O(n \log^2 n \cdot \max\{k, \log n \log k\})$ bits of space which improves upon the $O(kn \log^3 n)$-space algorithm of Ahn, Guha, and McGregor (SODA'12). For the values of $k$ that are truly sublinear, our space usage \emph{very nearly} matches the known lower bound $Ω(n \log^2 n \cdot \max\{k, \log n\})$ established by Nelson and Yu (SODA'19; implicit) and Robinson (DISC'24). In particular, our algorithm fully settles the space complexity at $Θ(kn \log^2{n})$ for $k = Ω(\log n \log \log n)$, and bridges the gap down to only a doubly-logarithmic factor of $O(\log \log n)$ for a smaller range of $k = o(\log n \log \log n)$.
Keywords
All Related Versions
This publication has 9 references indexed in Scilit:
- Directed and Undirected Vertex Connectivity Problems are Equivalent for Dense Graphs2026
- Deterministic Edge Connectivity in Near-Linear TimeJournal of the ACM, 2018
- Randomized Approximation Schemes for Cuts and Flows in Capacitated GraphsSIAM Journal on Computing, 2015
- On graph problems in a semi-streaming modelTheoretical Computer Science, 2005
- Sampling in dynamic data streams and applications2005
- Super-logarithmic depth lower bounds via direct sum in communication complexity2002
- Random Sampling in Cut, Flow, and Network Design ProblemsMathematics of Operations Research, 1999
- A new approach to the minimum cut problemJournal of the ACM, 1996
- Chernoff–Hoeffding Bounds for Applications with Limited IndependenceSIAM Journal on Discrete Mathematics, 1995