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.
^1
1
We 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.