## 3 Flows over Time  
### Basic Notions  
We are given a network, \((D,c,\tau)\), consisting of a directed graph, \(D\), some terminal vertices, \(S\subseteq V(D)\), and a capacity function, \(c:E(D)\rightarrow\mathbb{R}_{>0}\), on the edges. The last element is the _transit time_ function: \(\tau:E(D)\rightarrow\mathbb{Z}_{\geq 0}\). Besides these, an instance contains a _time horizon_, \(T\in\mathbb{Z}_{>0}\), as well. Loops and multiple edges are allowed in \(D\). **Definition 3.1** (flow over time). : _Functions, \(f_{e}:\{0,1,...,T-1\}\rightarrow\mathbb{R}_{\geq 0}\), for each edge \(e\in E(D)\) form a flow over time or dynamic flow with time horizon, \(T\), if they fulfill all of the following requirements:_  
1. \(f_{e}(\theta)=0\) _for_ \(\theta\geq T-\tau(e)\)__
2. _--this ensures that flow can be sent from_ \(u\) _along an edge,_ \(uv\)_, only if there is enough time left for it to reach_ \(v\)2. \(f_{e}(\theta)\leq c(e)\) _for all_ \(e\in E(D)\) _and_ \(\theta\in\{0,1,...,T-1\}\)__  
_--capacity constraints hold all the time._
3. \(\sum_{e\in\delta^{-}(v)}\sum_{\xi\leq\theta-\tau(e)}f_{e}(\xi)= \sum_{e\in\delta^{+}(v)}\sum_{\xi\leq\theta}f_{e}(\xi)\) _for all_ \(v\in V(D)\setminus S\) _and_ \(\theta\in\{0,1,...,T-1\}\)__  
_--flow conservation is fulfilled at every point in time._  
Any dynamic flow problem can be converted into an ordinary flow problem with the help of the _time-expanded network_, \(D^{T}\). We create \(T\) copies of \(V(D)\), with \(v_{i}\) denoting the \((i+1)\)th copy of vertex \(i\). For every edge, \(uv\in E(D)\), and every \(i\in\{0,\ldots,T-1-\tau(uv)\}\), we connect \(u_{i}\) with \(v_{i+\tau(uv)}\). The vertices of \(D^{T}\) with a fixed index, \(i\), form a _timeslot_. Though this construction reduces the flow over time concept to the static setting without transit times, the price of this simplification is a considerably larger time-expanded network, \(D^{T}\), having a size linear in \(T\) and, thus, exponential in the input size. This does not always cause a problem: in the maximum dynamic flow problem, there is always a temporally repeated maximum flow that can be found in polynomial time [7,8]. We extend the flow over a time instance to stable flows over time, by introducing preference lists. They have the same behavior as in the stable flow problem, and they do not change in time. The notion of stability can be extended to this instance the following way:  
**Definition 3.2** (stable flow over time). : _A directed walk, \(W=(v^{1},e^{1},...,e^{k-1},v^{k})\), is a blocking walk of flow over time, \(f\), if there is a certain point in time, \(0\leq\theta\leq T-1\), such that all the following properties hold:_  
1. _each edge,_ \(e^{i}\)_, is unsaturated at time_ \(\theta+\sum_{j=1}^{i-1}\tau(e^{j})\)__
2. \(v^{1}\in S\) _or there is an edge,_ \(e^{\prime}=v^{1}u\)_, such that_ \(f_{e^{\prime}}(\theta)>0\) _and_ \(e^{1}<_{v^{1}}e^{\prime}\)__
3. \(v^{k}\in S\) _or there is an edge,_ \(e^{\prime\prime}=wv^{k}\)_, such that_ \(f_{e^{\prime\prime}}\left(\theta+\sum_{j=1}^{k-1}\tau(e^{j})-\tau(e^{\prime \prime})\right)>0\) _and_ \(e^{k-1}<_{v^{k}}e^{\prime\prime}\)__  
A blocking walk, \(W\), can be interpreted in a similar way as in the static case: if the two participants symbolized by the end vertices agree that sending some flow along \(W\) would improve their situation, then the scheme will be broken by them. Note that a flow over time is stable, if and only if the corresponding flow in the time-expanded network is stable in the classical sense. **Theorem 3.3**. : _For every \((D,c,\tau,O)\) and time horizon, \(T\in\mathbb{Z}_{>0}\), there is a stable flow over time._  
Proof. : A stable static flow exists in the time-expanded network. **Corollary 3.4**. : _In every stable flow over time with \(T\in\mathbb{Z}_{>0}\), the terminal vertices send and receive the same amount of flow in a fixed timeslot on all edges incident to them._  
Proof. : This follows from Theorem 2.4. Note that these two statements hold, even if the preference lists may change in time. **Remark 3.5**.