## 3 Flows over Time
### Basic Notions
: _Without loss of generality, we can assume the graph to be simple and free of loops. If an edge, \(e\), is a loop or parallel to another edge, we simply split this edge into two edges, \(e_{1},e_{2}\), introducing a new vertex, \(v_{e}\). We assign capacities, \(c(e_{1})=c(e_{2})=c(e)\), and transit times, \(\tau(e_{1})=\tau(e)\) and \(\tau(e_{2})=0\), to the new edges. As \(v_{e}\) is a non-terminal and has only one incoming and one outgoing edge, it will never be the start or end vertex of a blocking walk. Furthermore, any blocking walk visiting \(v_{e}\) corresponds to a blocking walk in the original graph using the edge, \(e\), and vice versa._  
_As a result of this assumption, any propose or refuse operation on a vertex, \(v_{i}\), in the time-expanded network does not effect the state of any other copy, \(v_{j}\), of the same vertex._  
Time-expanded variant of the preflow-push algorithm:In order to obtain structural insights on stable flows over time, we will apply Algorithm 1 in the time expanded network using a special order of the vertices: it picks a vertex, \(v\in V\setminus S\), from the underlying static network and handles all copies of \(v\), starting at \(v_{0}\) and ending at \(v_{T-1}\), processing each of them as long as it has excessive flow. We will call such a traversal of all copies of a vertex, \(v\), by the algorithm a \(v\)_-phase_. The following lemma gives important structural insights on the stable flow computed by Algorithm 3, which will prove useful in the following sections. ```
Initialize \(p,r\). Saturate all edges, leaving \(S\). while\(\exists v\in V\setminus S:\ \sum_{i=0}^{T-1}\mathrm{ex}(v,f)>0\)do for\(i=0\) to \(T-1\)do while\(\mathrm{ex}(v_{i},f)>0\)do if\(p[v]\
eq 0\)then  propose(\(p[v_{i}]\)) else  refuse(\(r[v_{i}]\)) endif endwhile endfor endwhile
```  
**Algorithm 3** Time-expanded variant of the preflow-push algorithm. **Lemma 3.6**. : _Let \(i<j\). After every \(u\)-phase for any vertex, \(u\in V\setminus S\), in Algorithm 3, the following statements hold for all \(v\in V(D)\setminus S\):_  
1. \(p[v_{i}]\leq_{v}p[v_{j}]\)__
2. _If_ \(p[v_{i}]=_{v}p[v_{j}]=vw\) _and_ \(r[w_{j+\tau(vw)}]>_{w}vw\) _(or_ \(w\in S\)_), then_ \(f(p[v_{i}])\leq f(p[v_{j}])\)_._
3. \(r[v_{i}]\geq_{v}r[v_{j}]\)__
4. _If_ \(r[v_{i}]=_{v}r[v_{j}]\
eq 0\)_, then_ \(f(r[v_{i}])\geq f(r[v_{j}])\)_._  
Proof. : We prove the lemma by induction on the algorithm. Clearly, all statements are true after initialization. We show that they also stay true after the end of each phase. First, observe that during a \(u\)-phase, statements (a) to (d) cannot be invalidated for any vertex, \(v\
eq u\): The pointers of \(v\) are not changed, so (a) and (c) remain valid for \(v\). The flow on any edge, \(r[v_{i}]\), for any \(i\) cannot be changed, so (d) remains valid. Finally \(f(p[v_{i}])\) can only change if \(p[v_{i}]=r[u_{\ell}]\) for some index, \(\ell\), but in this case, (b) is always true. We thus can assume that after a phase of vertex \(v\), statements (a) to (d) are true for all vertices other than \(v\) and use this fact to show that they also hold for \(v\). Let \(i<j\), and consider the pointers of copies of vertex \(u\) and the flow on their incident edges after a \(u\)-phase. As there are no loops in the underlying graph, the algorithm ensures \(\mathrm{ex}(u_{i},f)=\mathrm{ex}(u_{j},f)=0\). Furthermore:  
\[f(u_{i}w_{i+\tau(e)})\geq f(u_{j}w_{j+\tau(e)})\quad\text{for all $e=uw\in E$ with $p[u_{i}]>_{u}uw$} \tag{1}\]  
(if \(u_{j}w_{j+\tau(e)}\) exists) because (c) and (d) hold for vertex \(w\). Likewise,  
\[f(w_{i-\tau(e)}u_{i})\leq f(w_{j-\tau(e)}u_{j})\quad\text{for all $e=wu\in E$ with $r[u_{j}]>_{u}wu$} \tag{2}\]  
(if \(w_{i-\tau(e)}u_{i}\) exists) because (a) and (b) hold for \(w\). Assume, by contradiction, that (a) or (b) is not valid after the phase. This implies \(r[u_{j}]=0\) and, thus, \(\mathrm{inflow}(u_{i})\leq\mathrm{inflow}(u_{j})\) by Equation (2), where \(\mathrm{inflow}(v)=\sum_{uv\in E(D)}f(uv)\). Let \(p[u_{i}]=_{u}e=uw\).