26.4 Pushrelabel algorithms
26.41
Prove that, after the procedure $\text{INITIALIZEPREFLOW}(G, S)$ terminates, we have $s.e \le f^*$, where $f^*$ is a maximum flow for $G$.
We apply the definition of excess flow (equation $\text{(26.14)}$) to the initial preflow $f$ created by $\text{INITIALIZEPREFLOW}$ (equation $\text{(26.15)}$) to obtain
$$ \begin{aligned} e(s) & = \sum_{v \in V} f(v, s)  \sum_{v \in V} f(s, v) \\ & = 0  \sum_{v \in V} c(s, v) \\ & = \sum_{v \in V} c(s, v). \end{aligned} $$
Now,
$$ \begin{aligned} f^* & = \sum_{v \in V} f^*(v, s)  \sum_{v \in V} f^*(s, v) \\ & \ge 0  \sum_{v \in V} c(s, v) \qquad \text{(since $f^*(v, s) \ge 0$ and $f^*(s, v) \le c(s, v)$)} \\ & = e(s). \end{aligned} $$
26.42
Show how to implement the generic pushrelabel algorithm using $O(V)$ time per relabel operation, $O(1)$ time per push, and $O(1)$ time to select an applicable operation, for a total time of $O(V^2E)$.
We must select an appropriate data structure to store all the information which will allow us to select a valid operation in constant time. To do this, we will need to maintain a list of overflowing vertices. By Lemma 26.14, a push or a relabel operation always applies to an overflowing vertex. To determine which operation to perform, we need to determine whether $u.h = v.h + 1$ for some $v \in N(u)$. We'll do this by maintaining a list $u.high$ of all neighbors of $u$ in $G_f$ which have height greater than or equal to $u$. We'll update these attributes in the $\text{PUSH}$ and $\text{RELABEL}$ functions. It is clear from the pseudocode given for $\text{PUSH}$ that we can execute it in constant time, provided we have maintain the attributes $\delta_f(u, v)$, $u.e$, $c_f(u, v)$, $(u, v).f$ and $u.h$. Each time we call $\text{PUSH}(u, v)$ the result is that $u$ is no longer overflowing, so we must remove it from the list.
Maintain a pointer $u.overflow$ to $u$'s position in the overflow list. If a vertex $u$ is not overflowing, set $u.overflow = \text{NIL}$. Next, check if $v$ became overflowing. If so, set $v.overflow$ equal to the head of the overflow list. Since we can update the pointer in constant time and delete from a linked list given a pointer to the element to be deleted in constant time, we can maintain the list in $O(1)$.
The $\text{RELABEL}$ operation takes $O(V)$ because we need to compute the minimum $v.h$ from among all $(u, v) \in E_f$, and there could be $V  1$ many such $v$. We will also need to update $u.high$ during $\text{RELABEL}$. When $\text{RELABEL}(u)$ is called, set $u.high$ equal to the empty list and for each vertex $v$ which is adjacent to $u$, if $v.h = u.h + 1$, add $u$ to the list $v.high$. Since this takes constant time per adjacent vertex we can maintain the attribute in $O(V)$ per call to relabel.
26.43
Prove that the generic pushrelabel algorithm spends a total of only $O(VE)$ time in performing all the $O(V^2)$ relabel operations.
Each time we call $\text{RELABEL}(u)$, we examine all edges $(u, v) \in E_f$. Since the number of relabel operations is at most $2V  1$ per vertex, edge $(u, v)$ will be examined during relabel operations at most $4V  2 = O(V)$ times (at most $2V  1$ times during calls to $\text{RELABEL}(u)$ and at most $2V  1$ times during calls to $\text{RELABEL}(v)$). Summing up over all the possible residual edges, of which there are at most $2E = O(E)$, we see that the total time spent relabeling vertices is $O(VE)$.
26.44
Suppose that we have found a maximum flow in a flow network $G = (V, E)$ using a pushrelabel algorithm. Give a fast algorithm to find a minimum cut in $G$.
We can find a minimum cut, given a maximum flow found in $G = (V, E)$ by a pushrelabel algorithm, in $O(V)$ time. First, find a height $\hat h$ such that $0 < \hat h < V$ and there is no vertex whose height equals $\hat h$ at termination of the algorithm. We need consider only $V  2$ vertices, since $s.h = V$ and $t.h = 0$. Because $\hat h$ can be one of at most $V  1$ possible values, we know that for at least one number in $1, 2, \ldots, V  1$, there will be no vertex of that height. Hence, $\hat h$ is well defined, and it is easy to find in $O(V)$ time by using a simple boolean array indexed by heights $1, 2, \ldots, V  1$.
Let $S = \{u \in V: u.h > \hat h\}$ and $T = \{v \in V: v.h < \hat h\}$. Because we know that $s.h = V > \hat h$, we have $s \in S$, and because $t.h = 0 < \hat h$, y we have $t \in T$, as required for a cut.
We need to show that $f(u, v) = c(u, v)$, i.e., that $(u, v) \notin E_f$, for all $u \in S$ and $v \in T$. Once we do that, we have that $f(S, T) = c(S, T)$, and by Corollary 26.5, $(S, T)$ is a minimum cut.
Suppose for the purpose of contradiction that there exist vertices $u \in S$ and $v \in T$ such that $(u, v) \in E_f$. Because $h$ is always maintained as a height function (Lemma 26.16), we have that $u.h \le v.h + 1$. But we also have $v.h < \hat h < u.h$, and because all values are integer, $v.h \le u.h  2$. Thus, we have $u.h \le v.h + 1 \le u.h  2 + 1 = u.h  1$, which gives the contradiction that $u.height \le u.height  1$. Thus, $(S, T)$ is a minimum cut.
26.45
Give an efficient pushrelabel algorithm to find a maximum matching in a bipartite graph. Analyze your algorithm.
First, construct the flow network for the bipartite graph as in the previous section. Then, we relabel everything in $L$. Then, we push from every vertex in $L$ to a vertex in $R$, so long as it is possible.
Keeping track of those that vertices of $L$ that are still overflowing can be done by a simple bit vector. Then, we relabel everything in R and push to the last vertex. Once these operations have been done, The only possible valid operations are to relabel the vertices of $L$ that weren't able to find an edge that they could push their flow along, so could possibly have to get a push back from $R$ to $L$. This continues until there are no more operations to do. This takes time of $O(V(E + V))$.
26.46
Suppose that all edge capacities in a flow network $G = (V, E)$ are in the set $\{1, 2, \ldots, k\}$. Analyze the running time of the generic pushrelabel algorithm in terms of $V$, $E$, and $k$. ($\textit{Hint:}$ How many times can each edge support a nonsaturating push before it becomes saturated?)
The number of relabel operations and saturating pushes is the same as before. An edge can handle at most $k$ nonsaturating pushes before it becomes saturated, so the number of nonsaturating pushes is at most $2kVE$. Thus, the total number of basic operations is at most $2V^2 + 2VE + 2kVE = O(kVE)$.
26.47
Show that we could change line 6 of $\text{INITIALIZEPREFLOW}$ to
1 6 s.h = G.V  2without affecting the correctness or asymptotic performance of the generic pushrelabel algorithm.
If we set $s.h = V  2$, we have to change our definition of a height function to allow $s.h = V  2$, rather than $s.h = V$. The only change we need to make to the proof of correctness is to update the proof of Lemma 26.17. The original proof derives the contradiction that $s.h \le k < V$, which is at odds with $s.h = V$. When $s.h = V  2$, there is no contradiction.
As in the original proof, let us suppose that we have a simple augmenting path $\langle v_0, v_1, \ldots, v_k \rangle$, where $v_0 = s$ and $v_k = t$, so that $k < V$. How could $(s, v_1)$ be a residual edge? It had been saturated in $\text{INITIALIZEPREFLOW}$, which means that we had to have pushed some flow from $v_1$ to $s$. In order for that to have happened, we must have had $v_1.h = s.h + 1$. If we set $s.h = V  2$, then $v_1.h$ was $V  1$ at the time. Since then, $v_1.h$ did not decrease, and so we have $v_1.h \ge V  1$. Working backwards over our augmenting path, we have $v_{k  i}.h \le t.h + i$ for $i = 0, 1, \ldots, k$. As before, because the augmenting path is simple, $k < V$. Letting $i = k  1$, we have $v_1.h \le t.h + k  1 < 0 + V  1$. We now have the contradiction that $v_1.h \ge V  1$ and $v_1.h < V  1$, which shows that Lemma 26.17 still holds.
Nothing in the analysis changes asymptotically.
26.48
Let $\delta_f(u, v)$ be the distance (number of edges) from $u$ to $v$ in the residual network $G_f$. Show that the $\text{GENERICPUSHRELABEL}$ procedure maintains the properties that $u.h < V$ implies $u.h \le \delta_f(u, t)$ and that $u.h \ge V$ implies $u.h  V \le \delta_f(u, s)$.
We'll prove the claim by induction on the number of push and relabel operations. Initially, we have $u.h = V$ if $u = s$ and $0$ otherwise. We have $s.h  V = 0 \le \delta_f(s, s) = 0$ and $u.h = 0 \le \delta_f(u, t)$ for all $u \ne s$, so the claim holds prior to the first iteration of the while loop on line 2 of the $\text{GENERICPUSHRELABEL}$ algorithm.
Suppose that the properties have been maintained thus far. If the next iteration is a nonsaturating push then the properties are maintained because the heights and existence of edges in the residual network are preserved. If it is a saturating push then edge $(u, v)$ is removed from the residual network, which increases both $\delta_f(u, t)$ and $\delta_f(u, s)$, so the properties are maintained regardless of the height of $u$.
Now suppose that the next iteration causes a relabel of vertex $u$. For all $v$ such that $(u, v) \in E_f$ we must have $u.h \le v.h$. Let $v' = \min\{v.h \mid (u,v) \in E_f\}$. There are two cases to consider.

First, suppose that $v.h < V$. Then after relabeling we have
$$u.h = 1 + v'.h \le 1 + \min_{(u, v)} \in E_f \delta_f(v, t) = \delta_f(u, t).$$

Second, suppose that $v'.h \ge V$. Then after relabeling we have
$$u.h = 1 + v'.h \le 1 + V + \min_{(u, v)} \in E_f \delta_f(v, s) = \delta_f(u, s) + V,$$
which implies that $u.h  V \le \delta_f(u, s)$.
Therefore, the $\text{GENERICPUSHRELABEL}$ procedure maintains the desired properties.
26.49 $\star$
As in the previous exercise, let $\delta_f(u, v)$ be the distance from $u$ to $v$ in the residual network $G_f$. Show how to modify the generic pushrelabel algorithm to maintain the property that $u.h < V$ implies $u.h = \delta_f(u, t)$ and that $u.h \ge V$ implies $u.h  V = \delta_f(u, s)$. The total time that your implementation dedicates to maintaining this property should be $O(VE)$.
What we should do is to, for successive backwards neighborhoods of $t$, relabel everything in that neighborhood. This will only take at most $O(VE)$ time (see 26.43). This also has the upshot of making it so that once we are done with it, every vertex's height is equal to the quantity $\delta_f(u, t)$. Then, since we begin with equality, after doing this, the inductive step we had in the solution to the previous exercise shows that this equality is preserved.
26.410
Show that the number of nonsaturating pushes executed by the $\text{GENERICPUSHRELABEL}$ procedure on a flow network $G = (V, E)$ is at most $4V^2E$ for $V \ge 4$.
Each vertex has maximum height $2V  1$. Since heights don't decrease, and there are $V  2$ vertices which can be overflowing, the maximum contribution of relabels to $\Phi$ over all vertices is $(2V  1)(V  2)$. A saturating push from $u$ to $v$ increases $\Phi$ by at most $v.h \le 2V  1$, and there are at most $2VE$ saturating pushes, so the total contribution over all saturating pushes to $\Phi$ is at most $(2V  1)(2VE)$. Since each nonsaturating push decrements $\Phi$ by at least on and $\Phi$ must equal zero upon termination, we must have that the number of nonsaturating pushes is at most
$$(2V  1)(V  2) + (2V  1)(2VE) = 4V^2E + 2V^2  5V + 3  2VE.$$
Using the fact that $E \ge V  1$ and $V \ge 4$ we can bound the number of saturating pushes by $4V^2E$.