We give an algorithm for computing exact maximum flows on graphs with $m$ edges and integer capacities in the range $[1, U]$ in $\widetilde{ 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 $\widetilde{ 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\k{ a}dry JACM `16]. This entails designing data structures that, in limited settings, return edges with large electric energy in a graph undergoing resistance updates.

Categories: cs.DS

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