Brief announcement: A special case of maximum flow over time with network changes
This work provides a theoretical framework for handling capacity changes in dynamic flow networks, which is relevant for applications like transportation and communication networks, though the approach is incremental as it builds on existing time-expanded network concepts.
The paper addresses the maximum flow over time problem in networks with time-varying edge capacities, proposing a condensed Time Expanded Network (cTEN) that reduces the problem to a standard max flow computation. For a graph with n nodes, m edges, and μ critical times, the cTEN has O(n²μ) nodes and O(μmn) edges, enabling solutions in O(μ²n³m) or O(μ^{(1+o(1))}(nm)^{1+o(1)} log(UT)) time.
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.