Authors: Mohsen Ghaffari, Jaehyun Koo

This paper presents the first parallel batch-dynamic algorithms for computing spanners and sparsifiers. Our algorithms process any batch of edge insertions and deletions in an $n$-node undirected graph, in $\text{poly}(\log n)$ depth and using amortized work near-linear in the batch size. Our concrete results are as follows:

  • Our base algorithm maintains a spanner with $(2k-1)$ stretch and $\tilde{O}(n^{1+1/k})$ edges, for any $k\geq 1$.
  • Our first extension maintains a sparse spanner with only $O(n)$ edges, and $\tilde{O}(\log n)$ stretch.
  • Our second extension maintains a $t$-bundle of spanners – i.e., $t$ spanners, each of which is the spanner of the graph remaining after removing the previous ones – and allows us to maintain cut/spectral sparsifiers with $\tilde{O}(n)$ edges.

Read original post