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 $\mathcal{C}$ of vertices $V$ such that the subgraphs of $G$ induced by the clusters $C \in \mathcal{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 $\tilde{O}(n/\epsilon\delta)$ space and edges, which we show is asymptotically tight up to polylogarithmic factors in $n$ for constant $\delta$.
翻译:在本文中, 我们开始研究 $G= (V, E) 图形的扩张器分解 $G = (V, E) 的计算流模式中 。 目标是在动态流流模型中找到一个使用小空间的递归性稀释进程。 我们的主要算法工具是一种新型的剪切变异器, 我们称它为电源剪除器 - 它将任何给定的脊椎引导子图( 或固定分配为 $V 的集聚) 的削减保持在$( delta,\ epslon) 至 $( $) 的递增/ addiplical $( $) 的典型构造。 在本文中, 我们第一次使用动态流模式中小空间的递增进程。 电源递解变异器作为恒定的磁盘 。