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] .
After revision:  We present an O(k ^2 n \log^3 n(nC) )-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] .