We give a randomized data structure for undirected weighted graphs that are partially dynamic, i.e., that undergo either only edge insertions or only edge deletions. The data structure maintains $(1\pm\epsilon)$-approximations to the maxflow value and effective resistance between any queried pair of vertices, with total update time $\widetilde{O}_{\epsilon}(n^2)$ and worst-case query time $\widetilde{O}_{\epsilon}(1)$. Thus, for dense graphs where $m = \Omega(n^2)$, our guarantees are near-optimal. Our algorithms succeed with high probability against an adaptive adversary. Our result follows from a simple stability principle for partially dynamic graphs. We show how to partition an online sequence of $m$ updates into $\widetilde{O}(n/\epsilon)$ epochs such that every graph within an epoch is a $(1\pm O(\epsilon))$-spectral approximation of the graph at the beginning of the epoch. The epochs are determined by the cumulative leverage score of the updated edges: small leverage-score mass implies small spectral change, while the total leverage-score mass over a monotone update sequence is $\widetilde{O}(n)$. Consequently, a spectral sparsifier needs to be recomputed only once per epoch. Applying known static all-pairs maxflow and effective-resistance oracles to these sparsifiers then yields the result.
Gramoz Goranci, Rasmus Kyng, Maximilian Probst Gutenberg et al.· 0 citations
We present a new solver-free parallel spectral sparsification algorithm for weighted graphs that relies only on parallel low-diameter decompositions and independent sampling. This yields the first algorithmic improvement over prior, solver-free parallel sparsification approaches since Koutis (2014) and, for the first time for a practical algorithm, eliminates any dependence on the target approximation accuracy ε in the algorithm's work and depth. Our algorithm works by sub-sampling edges according to their robust connectivity, as introduced by Kapralov and Panigrahy (2012). We show how to estimate the robust connectivities of G in an extremely simple manner: we create multiple random sub graphs Gp, where each edge in G is sub-sampled independently with probability pe = min {we · p, 1}. Then, we run a Low Diameter Decomposition in each of the graphs. If u and v often share a cluster in the LDDs, then this provides us with an upper bound on the robust connectivity of the edge e = (u,v). Carefully invoking this procedure for O (log n) different values of the probabilities p then allows us to obtain sufficiently good estimates for sub-sampling. We additionally complement the theory with an experimental evaluation demonstrating strong performance across relevant graphs and sparsity regimes.
Yves Baumann, Gernot Zöcklein· ACM Symposium on Parallelism...· 0 citations