\documentclass{article}
\input{6046preamble}


\begin{document}
\pset{7-1}{Dan Ports}{No collab}{Recitation \#8}

\begin{ppart}{Algorithm}
We show that it is possible to convert a fractional flow over a graph with integral capacities into an integral flow in $O(V E)$ time. We will do this by considering the residual network of the subgraph containing edges with fractional flow. It is easy to generate this subgraph by iterating through the edges and considering only the ones with fractional flow, then taking the residual network of this subgraph in $O(E)$ time. We will show that this residual network necessarily contains at least one cycle. We can therefore apply DFS to find the cycle (or determine that no cycles exist, in which case there are no edges in the residual network and we are done) in $O(V)$ time. Once we have done that, we can traverse the cycle (again in $O(V)$ time) and find the edge with minimum available capacity (call that capacity $C$). We then augment the original flow with the cycle we have just found, incrementing the flow through each edge by $C$ (or decreasing it if the flow in the original graph is in the opposite direction as the edge in the cycle). As we do so, if any edge now has an integral flow, we remove it from the fractional subgraph and its residual network. We repeat this procedure until the subgraph of edges with fractional flow is empty.
\end{ppart}

\begin{ppart}{Proof of correctness}
To justify the correctness of the algorithm, we first prove the claim that the residual network of the subgraph containing edges with fractional flow contains a cycle (if it is non-empty). To see this, consider any edge $e$ in the fractional subgraph, connecting vertex $u$ to vertex $v$ with maximum capacity $c$ and flow $f$. Since $c$ is an integer (by definition of the problem) and $f$ is fractional (because $e$ is in the fractional flow subgraph), we know $f$ is strictly less than $c$, though both nonzero. Then the residual network of that subgraph contains an edge from $u$ to $v$ with capacity $c-f$, as well as an edge in the opposite direction: from $v$ to $u$ with capacity $f$. This means that edges in the residual network exist in pairs: if there is an edge from $a$ to $b$, there is one from $b$ to $a$. Thus, for every vertex $v$ in the fractional subgraph, in-degree($v$) = out-degree($v$). Therefore if the fractional subgraph contains edges (i.e. if there are any edges with fractional flow), it must contain a cycle. In fact, by a result from a previous problem set, every connected component with more than one vertex contains an Euler tour, which is certainly a cycle.
\paragraph{}
Next we justify the correctness of the algorithm's path-augmenting loop. We will show that each iteration of the loop decreases the number of edges with fractional flow. We assume the correctness of the DFS-based algorithm for finding cycles that was presented in recitation. When we have found a cycle in the residual network of the fractional subgraph, we can certainly iterate through it to find the edge $e$ from $u$ to $v$ with minimum capacity $C$; i.e. every edge in the cycle has capacity greater than or equal to $C$. Then we can augment the original graph by increasing (or decreasing, depending on the direction of the edges in the residual network) the flow through each edge of the cycle by $C$. Since edge $e$ in the residual network had capacity $C$, we are guaranteed to have saturated $e$ in the residual network. This means that the edge between $u$ and $v$ in the original graph either has zero flow or is saturated. Since the maximum capacity of the edge is integral, we have thus ensured that the flow between $u$ and $v$ will now be integral, so at least one edge no longer has fractional flow. The algorithm certainly does not change any edge from integral flow to fractional flow, because it does not even consider, let alone change, any edge that is not on the subgraph of edges with fractional flow. Therefore the number of edges with fractional flow is strictly decreasing with each iteration of the loop, so it will eventually reach zero at which time the algorithm will terminate. Finally, we note that this process still generates a valid max-flow. It is certainly valid to augment the path by $C$ along the cycle, because we chose $C$ such that each edge on the residual network had capacity at least $C$. Notice that increasing every edge along a cycle by the same amount increases the flow into each vertex and the flow out of each vertex by the same amount. Thus, the flow continues to satisfy the flow conservation constraint. Moreover, the flow out of the source and into the sink is maintained invariant. Thus the algorithm correctly transforms the given fractional max-flow into an integral flow with the same value. This is the correct result.
\end{ppart}

\begin{ppart}{Runtime analysis}
The algorithm first needs to generate the fractional subgraph and its residual network. We showed above that this requires $O(V+E)$ time. Next we consider the work that is done during each iteration of the loop. We need to find a cycle by using DFS. Normally, DFS has runtime $O(V+E)$, but we can reduce this to $O(V)$ because we only need to continue searching until we find a cycle; there are only $V$ vertices, so once DFS has considered $V$ edges, it must have reached each vertex at least once, and thus we have found a cycle. The resulting cycle thus has $O(V)$ edges, so finding the minimum capacity of the edges takes $O(V)$ time, and incrementing the edges also takes $O(V)$ time. Thus each iteration of the loop requires $O(V)$ time. The loop cannot run more than $E$ times, because each iteration of the loop reduces the number of edges with fractional flow by at least one, and there cannot be more than $E$ edges with fractional flow to begin with. Thus the overall runtime of the algorithm is $O(VE)$.
\end{ppart}
\end{document}