Near-optimal Size Linear Sketches for Hypergraph Cut Sparsifiers
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910514330730496 |
|---|---|
| author | Khanna, Sanjeev Putterman, Aaron L. Sudan, Madhu |
| author_facet | Khanna, Sanjeev Putterman, Aaron L. Sudan, Madhu |
| contents | A $(1 \pm ε)$-sparsifier of a hypergraph $G(V,E)$ is a (weighted) subgraph that preserves the value of every cut to within a $(1 \pm ε)$-factor. It is known that every hypergraph with $n$ vertices admits a $(1 \pm ε)$-sparsifier with $\tilde{O}(n/ε^2)$ hyperedges. In this work, we explore the task of building such a sparsifier by using only linear measurements (a \emph{linear sketch}) over the hyperedges of $G$, and provide nearly-matching upper and lower bounds for this task.
Specifically, we show that there is a randomized linear sketch of size $\widetilde{O}(n r \log(m) / ε^2)$ bits which with high probability contains sufficient information to recover a $(1 \pm ε)$ cut-sparsifier with $\tilde{O}(n/ε^2)$ hyperedges for any hypergraph with at most $m$ edges each of which has arity bounded by $r$. This immediately gives a dynamic streaming algorithm for hypergraph cut sparsification with an identical space complexity, improving on the previous best known bound of $\widetilde{O}(n r^2 \log^4(m) / ε^2)$ bits of space (Guha, McGregor, and Tench, PODS 2015). We complement our algorithmic result above with a nearly-matching lower bound. We show that for every $ε\in (0,1)$, one needs $Ω(nr \log(m/n) / \log(n))$ bits to construct a $(1 \pm ε)$-sparsifier via linear sketching, thus showing that our linear sketch achieves an optimal dependence on both $r$ and $\log(m)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_03934 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Near-optimal Size Linear Sketches for Hypergraph Cut Sparsifiers Khanna, Sanjeev Putterman, Aaron L. Sudan, Madhu Data Structures and Algorithms A $(1 \pm ε)$-sparsifier of a hypergraph $G(V,E)$ is a (weighted) subgraph that preserves the value of every cut to within a $(1 \pm ε)$-factor. It is known that every hypergraph with $n$ vertices admits a $(1 \pm ε)$-sparsifier with $\tilde{O}(n/ε^2)$ hyperedges. In this work, we explore the task of building such a sparsifier by using only linear measurements (a \emph{linear sketch}) over the hyperedges of $G$, and provide nearly-matching upper and lower bounds for this task. Specifically, we show that there is a randomized linear sketch of size $\widetilde{O}(n r \log(m) / ε^2)$ bits which with high probability contains sufficient information to recover a $(1 \pm ε)$ cut-sparsifier with $\tilde{O}(n/ε^2)$ hyperedges for any hypergraph with at most $m$ edges each of which has arity bounded by $r$. This immediately gives a dynamic streaming algorithm for hypergraph cut sparsification with an identical space complexity, improving on the previous best known bound of $\widetilde{O}(n r^2 \log^4(m) / ε^2)$ bits of space (Guha, McGregor, and Tench, PODS 2015). We complement our algorithmic result above with a nearly-matching lower bound. We show that for every $ε\in (0,1)$, one needs $Ω(nr \log(m/n) / \log(n))$ bits to construct a $(1 \pm ε)$-sparsifier via linear sketching, thus showing that our linear sketch achieves an optimal dependence on both $r$ and $\log(m)$. |
| title | Near-optimal Size Linear Sketches for Hypergraph Cut Sparsifiers |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2407.03934 |