Fully Dynamic Electrical Flows: Sparse Maxflow Faster Than Goldberg-Rao

Abstract

We give an algorithm for computing exact maximum flows on graphs with $m$ edges and integer capacities in the range $[1,U]$ in $\tilde{O}(m^{\frac{3}{2}-\frac{1}{328}}\log U)$ time. For sparse graphs with polynomially bounded integer capacities, this is the first improvement over the $\tilde{O}(m^{1.5}\log U)$ time bound from [Goldberg-Rao JACM `98]. Our algorithm revolves around dynamically maintaining the augmenting electrical flows at the core of the interior point method based algorithm from [Mądry JACM `16]. This entails designing data structures that, in limited settings, return edges with large electric energy in a graph undergoing resistance updates.

78 pages, v2. Fixes an issue relating to handling of adaptivity and randomness -- we thank Aaron Sidford for discussions during which this error was pointed out