A (Very) Nearly Optimal Sketch for $k$-Edge Connectivity Certificates
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911218453708800 |
|---|---|
| author | Sawettamalya, Pachara Yu, Huacheng |
| author_facet | Sawettamalya, Pachara Yu, Huacheng |
| contents | 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)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_16336 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A (Very) Nearly Optimal Sketch for $k$-Edge Connectivity Certificates Sawettamalya, Pachara Yu, Huacheng Data Structures and Algorithms 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)$. |
| title | A (Very) Nearly Optimal Sketch for $k$-Edge Connectivity Certificates |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2510.16336 |