Generalized Flow in Nearly-linear Time on Moderately Dense Graphs

In this paper we consider generalized flow problems where there is an m-edge n-node directed graph $G=(V, E)$ and each edge $e \in E$ has a loss factor $\gamma_{e}\gt 0$ governing whether the flow is increased or decreased as it crosses edge e. We provide a randomized $\widetilde{O}\left(\left(m+n^{1.5}\right) \cdot \operatorname{polylog}\left(\frac{W}{\delta}\right)\right)$ time algorithm for solving the generalized maximum flow and generalized minimum cost flow problems in this setting where $\delta$ is the target accuracy and W is the maximum of all costs, capacities, and loss factors and their inverses. This improves upon the previous state-of-the-art $\widetilde{O}\left(m \sqrt{n} \cdot \log ^{2}\left(\frac{W}{\delta}\right)\right)$ time algorithm, obtained by combining the algorithm of [17] with techniques from [29]. To obtain this result we provide new dynamic data structures and spectral results regarding the matrices associated to generalized flows and apply them through the interior point method framework of [39].1.1The full version of this paper is available at https://arxiv.org/abs/2510.17740.