NUK - logo
E-viri
  • Gao, Yu; Liu, Yang P.; Peng, Richard

    2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), 2022-Feb.
    Conference Proceeding

    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.