Shuchi Chawla, Kristin Sheridan
We consider the problem of finding the value of a maximum flow over time in a network with uniform edge lengths where the edge capacities change at specific time instants. To solve this problem, we show how to construct a condensed version of a Time Expanded Network (cTEN) whose standard max flow value is the same as the max flow over time on the original network. In particular, for a graph with $n$ nodes, $m$ edges, and $μ$ {\em critical times} where some edge capacity changes, we obtain a cTEN with $O(n^2μ)$ nodes and $O(μmn)$ edges. This implies that the problem can be solved in $O(μ^2n^3m)$ time using the combinatorial max flow algorithm of Orlin [Orl13], or in $O(μ^{(1+o(1))}(nm)^{1+o(1)}\log (UT))$ time using the algorithm of Chen et al. [CKL+22], where $U$ is the maximum capacity of any edge and $T$ is the time horizon. We focus on graphs that experience many time changes across the period of interest, as in such graphs the $μ$ term dominates the runtime.