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² n · max{k, log n log k}) bits of space which improves upon the O(kn log³ 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 Ω(n log² n · 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² 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).