On the Streaming Complexity of Expander Decomposition

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.