Before revision:  We present an O(k ^2 n \log^3 n )-time algorithm that, given a directed k-apex graph G with n vertices, arc capacities, a set of sources S and a set of sinksT, computes a maximum flow from S to T in G . This improves by a factor of k on the fastest algorithm previously known for this problem [   Borradaile et al., FOCS 2012, SICOMP 2017] . Our improvement is achieved by introducing a new variant of the push-relabel algorithm for computing maximum flows.
After revision:  We present an O(k ^2 n \log^3 n )-time algorithm that, given a directed k-apex graph G with n vertices, arc capacities, a set of sources S and a set of sinksT, computes a maximum flow from S to T in G . This improves by a factor of k on the fastest algorithm previously known for this problem [ 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 for computing maximum flows.