{"ID":2853325,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.16336","arxiv_id":"2510.16336","title":"A (Very) Nearly Optimal Sketch for $k$-Edge Connectivity Certificates","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)$.","short_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$ t...","url_abs":"https://arxiv.org/abs/2510.16336","url_pdf":"https://arxiv.org/pdf/2510.16336v1","authors":"[\"Pachara Sawettamalya\",\"Huacheng Yu\"]","published":"2025-10-18T03:51:06Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}