Computing Flows in Subquadratic Space

Abstract

Space complexity is a critical factor in various computational models, including streaming, parallel/distributed computing, and communication complexity. We study the space complexity of the minimum-cost flow problem, a generalization of the st-max flow problem, focusing on computing flows in subquadratic space. In the general case with arbitrary capacities, minimum cost and $st$-maximum flows can use up to $Ω(n^2)$ edges, so computing the flow on each edge (rather than just the size/cost) seems impossible in subquadratic space. Indeed, there are lower bounds proving quadratic space is needed to store the flow on every edge, which has been used to prove lower bounds on streaming algorithms. However, we show that these lower bounds can be circumvented, opening up improvements for streaming and communication complexity. For a directed graph with integer capacities and costs bounded by $W$, we provide a $\tilde O(n^{1.5}\log (W/ε))$-space $\tilde O(\sqrt{n} \log(W/ε))$-pass streaming algorithm, which during the last pass returns the flow on each edge up to an additive error of $ε$. Crucially, the algorithm does not return the flow at the end of the last pass but returns the flow on an edge, as the edge is read in the stream. This allows us to circumvent existing $Ω(n^2)$ space lower bounds. In the 2-party communication model, our algorithm implies $\tilde O(n^{1.5}\log^2 W)$ bits of communication.

Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.