## 2 Stable Flows
### Algorithms to Find Stable Flows
while\(\exists v\in V(D)\setminus S:\ \mathrm{ex}(v,f)>0\)do for all\(v\in V(D):\ p[v]\
eq 0\)do  propose(\(p[v]\)) endfor for all\(v\in V(D):\ p[v]=0\)do  refuse(\(r[v]\)) endfor endwhile
```  
**Algorithm 3** Simultaneous push algorithm. ```
Initialize \(p,r\). Saturate all edges, leaving \(S\). while\(\exists v\in V(D)\setminus S:\ \mathrm{ex}(v,f)>0\)do for all\(v\in V(D):\ p[v]\
eq 0\)do  propose(\(p[v]\)) endfor for all\(v\in V(D):\ p[v]=0\)do  refuse(\(r[v]\)) endfor endwhile
```  
**Algorithm 4** Simultaneous push algorithm. ```
Initialize \(p,r\). Saturate all edges, leaving \(S\). while\(\exists v\in V(D)\setminus S:\ \mathrm{ex}(v,f)>0\)do  if\(p[v]\
eq 0\)then  propose(\(p[v]\)) else  advance(\(p[v]\)) endif endprocedure
```  
**Algorithm 5** Simultaneous push algorithm. A special execution of Algorithm 1 gives the McVitie-Wilson algorithm [9] for the stable marriage problem. We can determine the choice of active vertices, while running Algorithm 1 on the flow instance defined by the stable matching instance. At initialization, the source sends one unit of flow to each vertex, symbolizing a man. The active vertex chosen arbitrarily in the first step is one of them. He proposes along his best edge, and the asked woman accepts the offer and sends the flow further to the sink. Now, the second man will be chosen arbitrarily; he proposes along his best edge. If any woman gets more than one offer, her vertex enters the active set, and she needs to be chosen next. Afterwards, the refused man must play the role of the selected vertex, and so on. This way, we run the deferred-acceptance algorithm by taking the men one by one to the instance, always setting up a current stable matching. **Theorem 2.5**. : _If \(c\) is integral, both algorithms return an integral stable flow in at most \(O\left(\sum_{e\in E}c(e)\right)\) iterations._  
The proof is split into three parts:  
**Claim 1**. : _Throughout the course of the algorithms, \(f\) is integral._  
Proof. : We prove this by induction. The claim is true after initialization, as the capacities of all edges are integral. Thus, before a call of refuse or propose, the excess of the corresponding vertex is integral, as well. This implies that the flow value of the corresponding edge is changed by an integral amount. **Claim 2**. : _Both algorithms terminate after \(O\left(\sum_{e\in E}c(e)\right)\) steps._  
Proof. : In each call of propose, the flow value of the corresponding edge is increased by an integral amount (by claim 1), or the pointer \(p\) is advanced. Likewise, in each call of refuse, the flow value of the corresponding edge is decreased by an integral amount, or the pointer \(r\) is advanced. Once refuse is called for some edge, \(uv\), the flow value cannot be increased by a propose call anymore. Thus, there can be only at most \(O\left(\sum_{e\in E}c(e)\right)\) calls of propose and refuse. **Claim 3**. : _The algorithms return a stable flow._  
Proof. : After termination, \(f\) is a feasible flow, as the excess of every non-terminal vertex is zero. Now, suppose there is a blocking walk in the network. There are two reasons for leaving unsaturated edges in the network: either the edge was refused or there was no proposal along it using all its capacity; it stayed at least partly unexamined. We will study which case can come up at which position in the blocking walk. If an unsaturated walk starts at a terminal vertex, then the first edge of it has been refused, since \(s\in S\) must try to fill all its adjacent edges with maximum capacity. If the walk ends at a terminal vertex, there was no full proposal along that edge in the algorithm, since terminal vertices do not refuse any flow. If the blocking walk starts at a non-terminal vertex, then there must be a dominated edge starting at the same vertex and having nonzero value. This proves that the unsaturated edge has been refused, because vertices submit offers along edges in their order in the preference list of the start vertex.