A (Very) Nearly Optimal Sketch for k k -Edge Connectivity Certificates
Pachara Sawettamalya, Huacheng Yu · 2025
Read A (Very) Nearly Optimal Sketch for k k -Edge Connectivity Certificates by Pachara Sawettamalya, Huacheng Yu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-16336.txt.
Introduction
Pachara Sawettamalya and Huacheng Yu sharpen a space-saving method for certifying that a network stays connected. A k-edge connectivity certificate is a small subgraph with a big job. It keeps the full graph's connection strength, up to k edge failures. In a dynamic stream, edges come and go, and memory is tight.
Their simple algorithm stores the certificate using space that very nearly matches the known lower bound. For mid-to-large k it settles the space cost exactly, closing a question open since a 2012 algorithm used more room. For small k, only a tiny doubly-log factor of slack remains. Near-optimal sketches like this let huge, shifting networks be monitored from a trickle of memory.
Catalog record
| CREATOR | Pachara Sawettamalya, Huacheng Yu |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 35 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-16336
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A (Very) Nearly Optimal Sketch for k k -Edge Connectivity Certificates Pachara Sawettamalya, Huacheng Yu Abstract In this note, we present a simple algorithm for computing a k k -connectivity certificate in dynamic graph streams. Our algorithm uses O ( n log 2 n ⋅ max { k , log n log k } ) O(n\log^{2}n\cdot\max\{k,\log n\log k\}) bits of space which improves upon the O ( k n log 3 n ) O(kn\log^{3}n) -space algorithm of Ahn, Guha, and McGregor (SODA’12). For the values of k k that are truly sublinear, our space usage very nearly matches the known lower bound Ω ( n log 2 n ⋅ max { k , log n } ) \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 Θ ( k n log 2 n ) \Theta(kn\log^{2}{n}) for k = Ω ( log n log log n ) k=\Omega(\log n\log\log n) , and bridges the gap down to only a doubly-logarithmic factor of O ( log log n ) O(\log\log n) for a smaller range of k = o ( log n log log n ) k=o(\log n\log\log n) . 1 Introduction The problem of computing an edge-connectivity certificate concerns verifying whether a given graph satisfies a desired level of edge connectivity. Formally, given an n -vertex graph G=(V,E) and a target edge-connectivity parameter k\in\mathbb{N} , the goal is to produce an object that certifies whether G is k -edge-connected or not. In this work, we consider a notion of certificates that provide explicit evidence in either cases. Definition 1.1 ( k -Connectivity Certificate) . Let G=(V,E) be a graph on n vertices and let k be a positive integer. A k -connectivity certificate is one of the following: (+) If G is k -edge-connected, the certificate is a spanning subgraph H of G such that H itself is k -edge-connected. (-) If G is not k -edge-connected, the certificate consists of a cut (S,\overline{S}) whose cut size is strictly less than k , along with the explicit list of edges crossing the cut denoted by E(S,\overline{S}) . We study the problem of computing a k -connectivity certificate in the dynamic graph stream [ 10 ] where the input graph G is presented as a sequence of edge insertions and deletions. The algorithm must process the stream in a single pass while using limited memory. At the end of the stream, it is required to output a valid k -connectivity certificate, as defined previously. Problem 1.2 ( k -Connectivity Certificate in Dynamic Streams) . Given a connectivity parameter k\in\mathbb{N} and an n -vertex graph G presented as a stream of edge insertions and deletions, design a single-pass streaming algorithm that outputs a valid k -connectivity certificate of G . For the special case of k=1 , the problem indeed reduces to computing a spanning forest of the input graph G . The well-celebrated work of Ahn, Guha, and McGregor [ 1 ] shows that a spanning forest can be computed with high probability in the dynamic streaming model using only O(n\log^{3}n) space via an algorithm now known as the ‘‘AGM sketch’’. 1 1 1 Nelson and Yu [ 33 ] subsequently extends the AGM sketch to the regime of arbitrary error probability \delta using space O(n\log^{2}{n}\log(n/\delta)) . For general values of k , this idea can be extended by invoking the AGM sketch recursively, using a total space of O(kn\log^{3}n) . On the other hand, a space lower bound for certifying positive instances (i.e., the (+) case in the definition) can be derived via combining two prior results. First, Robinson [ 35 ] establishes a lower bound of \Omega(kn\log^{2}(n/k)) bits, even when the algorithm is required to succeed with only constant probability. Separately, Nelson and Yu [ 33 ] show that even the simpler task of outputting a spanning forest requires \Omega(n\log^{3}n) space, thereby establishing the optimality of the AGM sketch for the spanning forest problem. While this lower bound does not immediately translate to the question of k -connectivity certificate—due to differences in problem formulation—their techniques can be adapted in a white-box manner to show that any dynamic streaming algorithm that certifies positive instances must also use \Omega(n\log^{3}n) space. 2 2 2 More precisely, to prove the \Omega(n\log^{3}n) -space lower bound for spanning forest computation, Nelson and Yu construct a hard distribution over input graphs such that any algorithm computing a spanning forest must use at least \Omega(n\log^{3}n) bits of space. Upon closer inspection, a graph G drawn from this hard distribution is, with overwhelming probability, n^{\Omega(1)} -connected, thereby satisfying the premise of our positive instances. Together, these lower bounds leave an open gap of roughly O(\min\{k,\log n\}) compared to the O(kn\log^{3}{n}) -space algorithm by [ 1 ] . Our Contributions. We present a simple algorithm for computing a k -connectivity certificate with improved space complexity in the dynamic streaming model. Theorem 1.3 . There is a single-pass dynamic streaming algorithm that computes a k -connectivity certificate using O(n\log^{2}n\cdot\max\{k,\log n\log k\}) bits of space. The algorithm succeeds with probability at least 1-n^{-5} . This result very nearly closes the aforementioned gaps in space complexity. In particular, when the value of k satisfies \Omega(\log n\log\log n)\leq k\leq n^{1-\Omega(1)} , our algorithm matches the lower bound of [ 35 ] up to constant factors, settling the space complexity at \Theta(kn\log^{2}{n}) . In the regime where k=o(\log n\log\log n) , we achieve an upper bound of O(n\log^{3}{n}\log{k}) , leaving only a gap of O(\log k)\leq O(\log\log n) compared to the lower bound by [ 33 ] . We also highlight a by-product of our algorithm in the distributed sketching model. In this setting, the n -vertex graph G is partitioned among n players, each holding a single vertex along with its incident edges. All players simultaneously send messages to a central referee, who then computes a k -connectivity certificate of G . Our algorithm from Theorem 1.3 extends naturally to this setting, as captured in the following corollary. For brevity, we omit the details of this extension. Corollary 1.4 . There is a randomized distributed sketching algorithm in which each player sends a message of length O(\log^{2}n\cdot\max\{k,\log n\log k\}) to a central referee. With probability at least 1-n^{-5} , the referee can compute a k -connectivity certificate of the input graph. 1.1 Brief descriptions of our algorithm Previous Approaches. Nagamochi and Ibaraki [ 30 ] observed that a k -connectivity certificate can be constructed from a graph F=F_{1}\cup\cdots\cup F_{k} , where each F_{i} is an arbitrary spanning forest of the remaining graph G\setminus(F_{1}\cup\cdots\cup F_{i-1}) . More precisely, it can be shown that G is k -edge connected if and only if F is k -edge-connected. The seminal work of [ 1 ] utilizes this construction in a clever way: by maintaining k independent copies of the AGM sketch, one for recovering each F_{i} , we can obtain a k -connectivity certificate using O(kn\log^{3}n) space. A notable feature of