Almost-Tight Bounds on Preserving Cuts in Classes of Submodular Hypergraphs
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_ | 1866916132264345600 |
|---|---|
| author | Khanna, Sanjeev Putterman, Aaron L. Sudan, Madhu |
| author_facet | Khanna, Sanjeev Putterman, Aaron L. Sudan, Madhu |
| contents | Recently, a number of variants of the notion of cut-preserving hypergraph sparsification have been studied in the literature. These variants include directed hypergraph sparsification, submodular hypergraph sparsification, general notions of approximation including spectral approximations, and more general notions like sketching that can answer cut queries using more general data structures than just sparsifiers. In this work, we provide reductions between these different variants of hypergraph sparsification and establish new upper and lower bounds on the space complexity of preserving their cuts. At a high level, our results use the same general principle, namely, by showing that cuts in one class of hypergraphs can be simulated by cuts in a simpler class of hypergraphs, we can leverage sparsification results for the simpler class of hypergraphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_13151 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Almost-Tight Bounds on Preserving Cuts in Classes of Submodular Hypergraphs Khanna, Sanjeev Putterman, Aaron L. Sudan, Madhu Data Structures and Algorithms Recently, a number of variants of the notion of cut-preserving hypergraph sparsification have been studied in the literature. These variants include directed hypergraph sparsification, submodular hypergraph sparsification, general notions of approximation including spectral approximations, and more general notions like sketching that can answer cut queries using more general data structures than just sparsifiers. In this work, we provide reductions between these different variants of hypergraph sparsification and establish new upper and lower bounds on the space complexity of preserving their cuts. At a high level, our results use the same general principle, namely, by showing that cuts in one class of hypergraphs can be simulated by cuts in a simpler class of hypergraphs, we can leverage sparsification results for the simpler class of hypergraphs. |
| title | Almost-Tight Bounds on Preserving Cuts in Classes of Submodular Hypergraphs |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2402.13151 |