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

We give an algorithm for computing exact maximum flows on graphs with <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m</tex> edges and integer capacities in the range [ <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$1,U$</tex> ] in <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Õ(m3/2-1/328log U)</tex> time. 1 1 We use <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Õ(·)</tex> to suppress logarithmic factors in <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m</tex> . For sparse graphs with polynomially bounded integer capacities, this is the first improvement over the <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Õ(m1.5log U)</tex> 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.