论文标题
动态流中的扩展器分解
Expander Decomposition in Dynamic Streams
论文作者
论文摘要
在本文中，我们启动了计算流模型中图$ g =（v，e）$的扩展器分解的研究。目的是找到一个$ \ MATHCAL {c} $ v $的分区{C} $，以使clusters $ c \ in \ Mathcal {C} $引起的$ g $的子图是一个不错的扩展器，而集群边缘的数量很小。扩展器分解是通过递归将平衡的稀疏切割涂在输入图上的经典构建的。在本文中，我们首先使用动态流模型中的小空间进行了这种递归最稀少的切割过程。 我们的主要算法工具是一种新型的切割稀疏器，我们将其称为功率切割的弹药器 - 它可以在任何给定的顶点诱导的子图中（或在$ v $的固定分区中的任何群集）保留削减到$（δ，ε）$（δ，ε）$ - 乘法/附加误差，具有高概率。功率切割的弹脚使用$ \ tilde {o}（n/εδ）$ space and Edges，我们显示的是渐近的，以$ n $ in Consance $δ$ $ n $。
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 $(δ, ε)$-multiplicative/additive error with high probability. The power cut sparsifier uses $\tilde{O}(n/εδ)$ space and edges, which we show is asymptotically tight up to polylogarithmic factors in $n$ for constant $δ$.
