# Fast Dynamic Cuts, Distances and Effective Resistances via Vertex Sparsifiers

arXiv: https://arxiv.org/abs/2005.02368 · HTML: https://mlsanity.com/paper/2005.02368/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 May 2020.

## Built on by (most cited first, 1 of 1)

- [The Structural Complexity of Matrix-Vector Multiplication](https://mlsanity.com/paper/2502.21240/) (2025)

## Abstract (arXiv)

We present a general framework of designing efficient dynamic approximate algorithms for optimization on undirected graphs. In particular, we develop a technique that, given any problem that admits a certain notion of vertex sparsifiers, gives data structures that maintain approximate solutions in sub-linear update and query time. We illustrate the applicability of our paradigm to the following problems. (1) A fully-dynamic algorithm that approximates all-pair maximum-flows/minimum-cuts up to a nearly logarithmic factor in tildeO(n2/3) amortized time against an oblivious adversary, and tildeO(m3/4) time against an adaptive adversary. (2) An incremental data structure that maintains O(1)-approximate shortest path in no(1) time per operation, as well as fully dynamic approximate all-pair shortest path and transshipment in tildeO(n2/3+o(1)) amortized time per operation. (3) A fully-dynamic algorithm that approximates all-pair effective resistance up to an (1+ε) factor in tildeO(n2/3+o(1) ε-O(1)) amortized update time per operation. The key tool behind result (1) is the dynamic maintenance of an algorithmic construction due to Madry [FOCS' 10], which partitions a graph into a collection of simpler graph structures (known as j-trees) and approximately captures the cut-flow and metric structure of the graph. The O(1)-approximation guarantee of (2) is by adapting the distance oracles by [Thorup-Zwick JACM `05]. Result (3) is obtained by invoking the random-walk based spectral vertex sparsifier by [Durfee et al. STOC `19] in a hierarchical manner, while carefully keeping track of the recourse among levels in the hierarchy.