Unit Capacity Maxflow in Almost $O(m^{4/3})$ Time

We present an algorithm, which given any m-edge n-vertex directed graph with positive integer capacities at most U computes a maximum s-t flow for any vertices s and t in O(m4/3+o(1)U1/3) time. This improves upon the previous best running times of O(m11/8+o(1)U1/4) [1], Õ(m√nlogU) [2] and O(mn) [3] when the graph is not too dense and doesn't have large capacities. We build upon advances for sparse maxflow based on interior point methods [1], [4], [5]. Whereas these methods increase the energy of local ℓ2-norm minimizing electrical flows, we instead increase the Bregman divergence value of flows which minimize the Bregman divergence with respect to a weighted log barrier. This allows us to trace the central path with progress depending only on ℓ∞norm bounds on the congestion vector as opposed to the ℓ4norm, which arises in these prior works. Further, we show that smoothed ℓ2-ℓpflows [6], [7] which were used to maximize energy [1] can also be used to efficiently maximize divergence, thereby yielding our desired runtimes. We believe our approach towards Bregman divergences of barriers may be of further interest.