

























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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。