Faster Maxflow via Improved Dynamic Spectral Vertex Sparsifiers

Understand

We make several advances broadly related to the maintenance of electrical flows in weighted graphs undergoing dynamic resistance updates, including: 1.

• More efficient dynamic spectral vertex sparsification, achieved by faster length estimation of random walks in weighted graphs using Morris counters [Morris 1978, Nelson-Yu 2020].
• 2.
• A direct reduction from detecting edges with large energy in dynamic electric flows to dynamic spectral vertex sparsifiers.