Expander Pruning with Polylogarithmic Worst-Case Recourse and Update Time

Expander graphs are known to be robust to edge deletions in the following sense: for any online sequence of edge deletions e 1 , e 2 , . . . , e k to an m-edge graph G that is initially a ϕexpander, the algorithm can grow a set P ⊆ V such that at any time t, G[V P ] is an expander of the same quality as the initial graph G up to a constant factor and the set P has volume at most O(t/ϕ). However, currently, there is no algorithm to grow P with low worst-case recourse that achieves any non-trivial guarantee.

In this work, we present an algorithm that achieves near-optimal guarantees: we give an algorithm that grows P only by Õ(1/ϕ 2 ) vertices per time step and ensures that G[V P ] remains Ω(ϕ)-expander at any time. 1 Even more excitingly, our algorithm is extremely efficient: it can process each update in near-optimal worst-case update time Õ(1/ϕ 2 ). This affirmatively answers the main open question posed in [SW19] whether such an algorithm exists.

By combining our results with recent techniques in [BvdBPG + 22], we obtain the first adaptive algorithms to maintain spanners, cut and spectral sparsifiers with Õ(n) edges and polylogarithmic approximation guarantees, worst-case update time and recourse. More generally, we believe that worst-case pruning is an essential tool for obtaining worst-case guarantees in dynamic graph algorithms and online algorithms.