Maintaining Expander Decompositions via Sparse Cuts
share
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, S̅) is ϕ-sparse if |E_G(S, S̅)| < ϕ·min{vol_G(S), vol_G(S̅)}. A ϕ-expander decomposition of G is a partition of V into sets X_1, X_2, …, X_k such that each cluster G[X_i] contains no ϕ-sparse cut (meaning it is a ϕ-expander) with Õ(ϕ 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 achieves the first sublinear ϕ m^o(1) recourse bounds on the number of edges to become crossing between clusters. Our techniques also give by far the simplest, deterministic algorithms for maintaining Strongly-Connected Components (SCCs) in directed graphs undergoing edge deletions, and for maintaining connectivity in undirected fully-dynamic graphs, both matching the current state-of-the-art run-times up to subpolynomial factors.
READ FULL TEXT