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

In this note, we present a simple algorithm for computing a \(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 very nearly matches the known lower bound \(\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 \(\Theta(kn\log^2 n)\) for \(k = \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)\).