论文标题
通过稀疏切割维持扩展器分解
Maintaining Expander Decompositions via Sparse Cuts
论文作者
论文摘要
在本文中，我们表明，通过反复删除稀疏切割，可以将膨胀删除的图表保持在图表中的算法可以有效。正式地，对于$ m $ - edge的无向图$ g $，我们说cut $（s，\ overline {s}）$是$ ϕ $ -sparse，如果$ | e_g（s，\ overline {s}）| <ϕ \ cdot \ min \ {vol_g（s），vol_g（\ overline {s}）\} $。 A $ϕ$-expander decomposition of $G$ is a partition of $V$ into sets $X_1, X_2, \ldots, X_k$ such that each cluster $G[X_i]$ contains no $ϕ$-sparse cut (meaning it is a $ϕ$-expander) with $\tilde{O}(ϕm)$ edges crossing between clusters.计算$ ϕ $ expander分解的一种自然方法是将簇分解为$ ϕ $ -sparse削减，直到任何群集中都没有这种切割为止。我们表明，即使在经历边缘删除的图表中，可以通过摊销更新时间$ m^{o（1）}/ϕ^2 $有效地实现此meta-Algorithm的轻微放松。我们的方法自然扩展到维护定向的$ ϕ $ - expander分解和$ ϕ $ - expander层次结构，因此给出了一个统一的框架，同时拥有比以前的最新作品更简单的证明。在所有设置中，我们的算法都与以前的算法的运行时间与多项式因素相匹配。此外，我们的算法为$ ϕ $ - expander分解提供了更强的保证。例如，对于进行边缘删除的图表，我们的方法是第一个保持动态扩展器分解的方法，其中每个更新的分解是对先前分解的细化，我们的方法是第一个保证sublinear $ ϕm^{1+o（1）$ bounter cross cross cross cross cross cross crots cross跨越整个序列的动态序列更新。
In this article, we show that the algorithm of maintaining expander decompositions in graphs undergoing edge deletions directly by removing sparse cuts repeatedly can be made efficient. Formally, for an $m$-edge undirected graph $G$, we say a cut $(S, \overline{S})$ is $ϕ$-sparse if $|E_G(S, \overline{S})| < ϕ\cdot \min\{vol_G(S), vol_G(\overline{S})\}$. A $ϕ$-expander decomposition of $G$ is a partition of $V$ into sets $X_1, X_2, \ldots, X_k$ such that each cluster $G[X_i]$ contains no $ϕ$-sparse cut (meaning it is a $ϕ$-expander) with $\tilde{O}(ϕm)$ edges crossing between clusters. A natural way to compute a $ϕ$-expander decomposition is to decompose clusters by $ϕ$-sparse cuts until no such cut is contained in any cluster. We show that even in graphs undergoing edge deletions, a slight relaxation of this meta-algorithm can be implemented efficiently with amortized update time $m^{o(1)}/ϕ^2$. Our approach naturally extends to maintaining directed $ϕ$-expander decompositions and $ϕ$-expander hierarchies and thus gives a unifying framework while having simpler proofs than previous state-of-the-art work. In all settings, our algorithm matches the run-times of previous algorithms up to subpolynomial factors. Moreover, our algorithm provides stronger guarantees for $ϕ$-expander decompositions. For example, for graphs undergoing edge deletions, our approach is the first to maintain a dynamic expander decomposition where each updated decomposition is a refinement of the previous decomposition, and our approach is the first to guarantee a sublinear $ϕm^{1+o(1)}$ bound on the total number of edges that cross between clusters across the entire sequence of dynamic updates.
