Expander Decomposition in Dynamic Streams

In this paper we initiate the study of expander decompositions of a graph G = ( V, E) in the streaming model of computation. The goal is to find a partitioning C of vertices V such that the subgraphs of G induced by the clusters C is an element of C are good expanders, while the number of intercluster edges is small. Expander decompositions are classically constructed by a recursively applying balanced sparse cuts to the input graph. In this paper we give the first implementation of such a recursive sparsest cut process using small space in the dynamic streaming model. Our main algorithmic tool is a new type of cut sparsifier that we refer to as a power cut sparsifier - it preserves cuts in any given vertex induced subgraph (or, any cluster in a fixed partition of V) to within a (delta, epsilon)-multiplicative/additive error with high probability. The power cut sparsifier uses (O) over tilde (n/epsilon delta) space and edges, which we show is asymptotically tight up to polylogarithmic factors in n for constant delta.