On the Streaming Complexity of Expander Decomposition
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911892367212544 |
|---|---|
| author | Chen, Yu Kapralov, Michael Makarov, Mikhail Mazzali, Davide |
| author_facet | Chen, Yu Kapralov, Michael Makarov, Mikhail Mazzali, Davide |
| contents | In this paper we study the problem of finding $(ε, ϕ)$-expander decompositions of a graph in the streaming model, in particular for dynamic streams of edge insertions and deletions. The goal is to partition the vertex set so that every component induces a $ϕ$-expander, while the number of inter-cluster edges is only an $ε$ fraction of the total volume. It was recently shown that there exists a simple algorithm to construct a $(O(ϕ\log n), ϕ)$-expander decomposition of an $n$-vertex graph using $\widetilde{O}(n/ϕ^2)$ bits of space [Filtser, Kapralov, Makarov, ITCS'23]. This result calls for understanding the extent to which a dependence in space on the sparsity parameter $ϕ$ is inherent. We move towards answering this question on two fronts. We prove that a $(O(ϕ\log n), ϕ)$-expander decomposition can be found using $\widetilde{O}(n)$ space, for every $ϕ$. At the core of our result is the first streaming algorithm for computing boundary-linked expander decompositions, a recently introduced strengthening of the classical notion [Goranci et al., SODA'21]. The key advantage is that a classical sparsifier [Fung et al., STOC'11], with size independent of $ϕ$, preserves the cuts inside the clusters of a boundary-linked expander decomposition within a multiplicative error. Notable algorithmic applications use sequences of expander decompositions, in particular one often repeatedly computes a decomposition of the subgraph induced by the inter-cluster edges (e.g., the seminal work of Spielman and Teng on spectral sparsifiers [Spielman, Teng, SIAM Journal of Computing 40(4)], or the recent maximum flow breakthrough [Chen et al., FOCS'22], among others). We prove that any streaming algorithm that computes a sequence of $(O(ϕ\log n), ϕ)$-expander decompositions requires ${\widetildeΩ}(n/ϕ)$ bits of space, even in insertion only streams. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_16701 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On the Streaming Complexity of Expander Decomposition Chen, Yu Kapralov, Michael Makarov, Mikhail Mazzali, Davide Data Structures and Algorithms In this paper we study the problem of finding $(ε, ϕ)$-expander decompositions of a graph in the streaming model, in particular for dynamic streams of edge insertions and deletions. The goal is to partition the vertex set so that every component induces a $ϕ$-expander, while the number of inter-cluster edges is only an $ε$ fraction of the total volume. It was recently shown that there exists a simple algorithm to construct a $(O(ϕ\log n), ϕ)$-expander decomposition of an $n$-vertex graph using $\widetilde{O}(n/ϕ^2)$ bits of space [Filtser, Kapralov, Makarov, ITCS'23]. This result calls for understanding the extent to which a dependence in space on the sparsity parameter $ϕ$ is inherent. We move towards answering this question on two fronts. We prove that a $(O(ϕ\log n), ϕ)$-expander decomposition can be found using $\widetilde{O}(n)$ space, for every $ϕ$. At the core of our result is the first streaming algorithm for computing boundary-linked expander decompositions, a recently introduced strengthening of the classical notion [Goranci et al., SODA'21]. The key advantage is that a classical sparsifier [Fung et al., STOC'11], with size independent of $ϕ$, preserves the cuts inside the clusters of a boundary-linked expander decomposition within a multiplicative error. Notable algorithmic applications use sequences of expander decompositions, in particular one often repeatedly computes a decomposition of the subgraph induced by the inter-cluster edges (e.g., the seminal work of Spielman and Teng on spectral sparsifiers [Spielman, Teng, SIAM Journal of Computing 40(4)], or the recent maximum flow breakthrough [Chen et al., FOCS'22], among others). We prove that any streaming algorithm that computes a sequence of $(O(ϕ\log n), ϕ)$-expander decompositions requires ${\widetildeΩ}(n/ϕ)$ bits of space, even in insertion only streams. |
| title | On the Streaming Complexity of Expander Decomposition |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2404.16701 |