2025/04/01 by Simon Meierhans, Maximilian Probst Gutenberg, Meierhans, Simon +3
Computer Science · #Complexity and Algorithms in Graphs #Advanced Graph Theory Research #Distributed systems and fault tolerance
paper · pdf · doi:10.48550/arxiv.2504.00544
Expander graphs are known to be robust to edge deletions in the following sense: for any online sequence of edge deletions e1, e2, …, ek 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 O(1/ϕ2) vertices per time step and ensures that G[V ∖ P] remains Ω(ϕ)-expander at any time. Even more excitingly, our algorithm is extremely efficient: it can process each update in near-optimal worst-case update time O(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 O(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.