Faster Algorithm for Maximum Flow in Directed Planar Graphs with Vertex Capacities

We give an $O(k^3 n \ \textrm{polylog}(nC))$-time algorithm for computing maximum integer flows in planar graphs with integer arc and vertex capacities bounded by $C$, and $k$ sources and sinks. This improves by a factor of $k^2$ over the fastest algorithm previously known for this problem [Wang, SODA 2019]. The speedup is obtained by two independent ideas. First we replace an iterative procedure of Wang that uses $k$ invocations of a maximum flow algorithm in a planar graph with $k$ apices [Borradaile et al., FOCS 2012, SICOMP 2017], by an alternative procedure that only makes one invocation of the algorithm of Borradaile et al. Second, we introduce a new variant of the push-relabel algorithm of Goldberg and Tarjan and use it to find a maximum flow in the $k$-apex graphs that arise in Wang's procedure, faster than the algorithm of Borradaile et al.