Flow variation over time is an important feature in network flow problems arising in various applications such as road or
air traffic control, production systems, communication networks (e.g., the Internet), and financial flows. The common characteristic
are networks with capacities and transit times on the arcs which specify the amount of time it takes for flow to travel through
a particular arc. Moreover, in contrast to static flow problems, flow values on arcs may change with time in these networks.
While the ‘maximum s-t-flow over time’ problem can be solved efficiently and ‘min-cost flows over time’ are known to be NP-hard, the complexity
of (fractional) ‘multicommodity flows over time’ has been open for many years. We prove that this problem is NP-hard, even
for series-parallel networks, and present new and efficient algorithms under certain assumptions on the transit times or on
the network topology. As a result, we can draw a complete picture of the complexity landscape for flow over time problems.
Keywords network flow - routing - flow over time - dynamic flow - complexity - efficient algorithm
Supported by the joint Berlin/Zurich graduate program Combinatorics, Geometry, and Computation (CGC), financed by ETH Zurich
and the German Science Foundation (DFG)
Supported in part by the EU Thematic Networks APPOL I & II, Approximation and Online Algorithms, IST-1999-14084, IST-2001-30012.