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

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.11We use$\tilde{O}(\cdot)$to suppress logarithmic factors in$m$. 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.