## 3 Flows over Time
### Infinite Time  
In this section, we will prove the existence of a stable flow, even if the time horizon is infinite. This flow can be constructed by applying the time-expanded preflow-push algorithm on \(D^{\infty}\) (under the assumption that it can apply the propose and refuse steps on all copies of a vertex in finite time). Even more, after a certain point in time, the stable flow is identical to a temporal repetition of the stable flow computed by the same algorithm in the static network, \(D\). We define \(D^{\infty}_{i}\) to be the subgraph induced by the vertices, \(v_{j}\) with \(j>i\). We will run Algorithm 1 on \(D\) and Algorithm 3 on \(D^{\infty}\) in parallel, executing a \(u\)-phase in \(D^{\infty}\) whenever vertex \(u\) is processed in \(D\). (Note that the state of vertex \(u_{i}\) does not, in particular, depend on any other vertex copy, \(u_{j}\), with \(j>i\). Therefore, the state of \(u_{i}\) and its adjacent edges after the \(u\)-phase is well defined, although infinitely many copies of \(u\) are processed during the \(u\)-phase.) Let \(f\) be the flow values in \(D\) and \(f^{\prime}\) be the flow values in \(D^{\infty}\) that occur throughout the run of the algorithm, and let \(p,r\) and \(p^{\prime},r^{\prime}\) be the corresponding pointers, respectively. Our main theorem in this section states that there is a point in time from which on all computations in the infinite time expanded network correspond one-to-one to those in the static network. **Theorem 3.7**. : _There is a point in time, \(0\leq i<\infty\), such that at the end of every \(u\)-phase for any vertex, \(u\), throughout the course of the algorithm, for every \(j\geq i\), \(f^{\prime}(v_{j}w_{j+\tau(vw)})=f(uv)\) for all edges \(vw\in E(D)\), and \(p^{\prime}[v_{j}]=_{v}p[v]\) and \(r^{\prime}[v_{j}]=_{v}r[v]\) for all \(v\in V(D)\)._  
Proof. : Let \(\tau_{\max}:=\max_{e\in E(D)}\tau(e)\). We will first prove by induction that until phase \(K\), the statement of the theorem is true for \(i_{K}:=K\cdot\tau_{\max}\). Clearly, this is true after initialization, as all edges leaving the terminal set are saturated, and all pointers are at their initial state. Now assume that after phase \(K\), the state of all flow variables and pointers in \(D^{\infty}_{i_{K}}\) is identical to that in \(D\). Now, let \(u\in V(D)\setminus S\) be the vertex that is processed in the current phase and let \(j>i_{K+1}\). Note that before the execution of the \(u\)-phase, all edges incident to \(u\) carry the same flow as all edges incident to \(u\) in \(D\) (as \(j-\tau_{\max}>i_{K}\)), and \(p^{\prime}[u_{j}]=p[u]\) and \(r^{\prime}[u_{j}]=r[u]\). Therefore, the \(u\)-phase modifies \(u_{j}\) and its incident edges in exactly the same way as \(u\) is modified by Algorithm 1 in \(D\). Accordingly, after the end of the \(u\)-phase, the statement of the theorem still holds for \(i_{K+1}\). We now have shown that up to phase \(K\), the statement of the theorem holds for \(i_{K}\). Now, let \(K_{0}\) be the number of iterations performed by Algorithm 1 before \(f\) is a stable flow in \(D\). After iteration \(K_{0}\), no flow values or pointers in \(D\) are changed. Let \(i:=i_{K_{0}+1}\). We will show that after iteration \(K_{0}\), also, no flow values or pointers in \(D^{\infty}_{i}\) are changed, which concludes the proof of the theorem. After iteration \(K_{0}\), all vertices in \(D^{\infty}_{i}\) are inactive. Thus, their state can only change if the flow value on an edge, \(v_{k}w_{l}\), for \(k<i\) and \(l\geq i\), is increased. This can only happen, if \(f^{\prime}(v_{k}w_{l})<c(vw)\), as well as \(r^{\prime}[w_{l}]>_{w}vw\), and \(p[v_{k}]=_{v}vw\). Note that at the end of the phase, \(K_{0}\), we have \(f^{\prime}(v_{k+\tau_{\max}}w_{l+\tau_{\max}})=f^{\prime}(v_{k}w_{l})\), and \(r^{\prime}[w_{l+\tau_{\max}}]=_{w}r^{\prime}[w_{l}]>_{w}vw\), by choice of \(i=i_{K_{0}+1}\).