A (Very) Nearly Optimal Sketch for $k$-Edge Connectivity Certificates

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 $\mathrm{\Omega }(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 $\mathrm{\Theta }(kn{\log }^{2}n)$ for $k=\mathrm{\Omega }(\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)$.