Computing Flows in Subquadratic Space
For researchers in streaming and communication complexity, this work provides the first subquadratic-space algorithm for computing flows on all edges, enabling new improvements in these areas.
The paper presents a streaming algorithm for the minimum-cost flow problem that uses subquadratic space (O~(n^{1.5})) and returns each edge's flow with additive error epsilon, circumventing previous quadratic space lower bounds by outputting flow during the stream rather than at the end.
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.