Near-optimal Hypergraph Sparsification in Insertion-only and Bounded-deletion Streams
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916702889967616 |
|---|---|
| author | Khanna, Sanjeev Putterman, Aaron Sudan, Madhu |
| author_facet | Khanna, Sanjeev Putterman, Aaron Sudan, Madhu |
| contents | We study the problem of constructing hypergraph cut sparsifiers in the streaming model where a hypergraph on $n$ vertices is revealed either via an arbitrary sequence of hyperedge insertions alone ({\em insertion-only} streaming model) or via an arbitrary sequence of hyperedge insertions and deletions ({\em dynamic} streaming model). For any $ε\in (0,1)$, a $(1 \pm ε)$ hypergraph cut-sparsifier of a hypergraph $H$ is a reweighted subgraph $H'$ whose cut values approximate those of $H$ to within a $(1 \pm ε)$ factor. Prior work shows that in the static setting, one can construct a $(1 \pm ε)$ hypergraph cut-sparsifier using $\tilde{O}(nr/ε^2)$ bits of space [Chen-Khanna-Nagda FOCS 2020], and in the setting of dynamic streams using $\tilde{O}(nr\log m/ε^2)$ bits of space [Khanna-Putterman-Sudan FOCS 2024]; here the $\tilde{O}$ notation hides terms that are polylogarithmic in $n$, and we use $m$ to denote the total number of hyperedges in the hypergraph. Up until now, the best known space complexity for insertion-only streams has been the same as that for the dynamic streams. This naturally poses the question of understanding the complexity of hypergraph sparsification in insertion-only streams.
Perhaps surprisingly, in this work we show that in \emph{insertion-only} streams, a $(1 \pm ε)$ cut-sparsifier can be computed in $\tilde{O}(nr/ε^2)$ bits of space, \emph{matching the complexity} of the static setting. As a consequence, this also establishes an $Ω(\log m)$ factor separation between the space complexity of hypergraph cut sparsification in insertion-only streams and dynamic streams, as the latter is provably known to require $Ω(nr \log m)$ bits of space. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_16321 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Near-optimal Hypergraph Sparsification in Insertion-only and Bounded-deletion Streams Khanna, Sanjeev Putterman, Aaron Sudan, Madhu Data Structures and Algorithms We study the problem of constructing hypergraph cut sparsifiers in the streaming model where a hypergraph on $n$ vertices is revealed either via an arbitrary sequence of hyperedge insertions alone ({\em insertion-only} streaming model) or via an arbitrary sequence of hyperedge insertions and deletions ({\em dynamic} streaming model). For any $ε\in (0,1)$, a $(1 \pm ε)$ hypergraph cut-sparsifier of a hypergraph $H$ is a reweighted subgraph $H'$ whose cut values approximate those of $H$ to within a $(1 \pm ε)$ factor. Prior work shows that in the static setting, one can construct a $(1 \pm ε)$ hypergraph cut-sparsifier using $\tilde{O}(nr/ε^2)$ bits of space [Chen-Khanna-Nagda FOCS 2020], and in the setting of dynamic streams using $\tilde{O}(nr\log m/ε^2)$ bits of space [Khanna-Putterman-Sudan FOCS 2024]; here the $\tilde{O}$ notation hides terms that are polylogarithmic in $n$, and we use $m$ to denote the total number of hyperedges in the hypergraph. Up until now, the best known space complexity for insertion-only streams has been the same as that for the dynamic streams. This naturally poses the question of understanding the complexity of hypergraph sparsification in insertion-only streams. Perhaps surprisingly, in this work we show that in \emph{insertion-only} streams, a $(1 \pm ε)$ cut-sparsifier can be computed in $\tilde{O}(nr/ε^2)$ bits of space, \emph{matching the complexity} of the static setting. As a consequence, this also establishes an $Ω(\log m)$ factor separation between the space complexity of hypergraph cut sparsification in insertion-only streams and dynamic streams, as the latter is provably known to require $Ω(nr \log m)$ bits of space. |
| title | Near-optimal Hypergraph Sparsification in Insertion-only and Bounded-deletion Streams |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2504.16321 |