26.4 Push-relabel algorithms
26.4-1
Prove that, after the procedure $\text{INITIALIZE-PREFLOW}(G, S)$ terminates, we have $s.e \le -|f^*|$, where $f^*$ is a maximum flow for $G$.
(Removed)
26.4-2
Show how to implement the generic push-relabel 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.4-3
Prove that the generic push-relabel algorithm spends a total of only $O(VE)$ time in performing all the $O(V^2)$ relabel operations.
(Removed)
26.4-4
Suppose that we have found a maximum flow in a flow network $G = (V, E)$ using a push-relabel algorithm. Give a fast algorithm to find a minimum cut in $G$.
(Removed)
26.4-5
Give an efficient push-relabel 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.4-6
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 push-relabel 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 $2k|V||E|$. Thus, the total number of basic operations is at most $2|V|^2 + 2|V||E| + 2k|V||E| = O(kVE)$.
26.4-7
Show that we could change line 6 of $\text{INITIALIZE-PREFLOW}$ to
without affecting the correctness or asymptotic performance of the generic pushrelabel algorithm.
(Removed)
26.4-8
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{GENERIC-PUSH-RELABEL}$ 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{GENERIC-PUSH-RELABEL}$ 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{GENERIC-PUSH-RELABEL}$ procedure maintains the desired properties.
26.4-9 $\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 push-relabel 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.4-3). 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.4-10
Show that the number of nonsaturating pushes executed by the $\text{GENERIC-PUSH-RELABEL}$ procedure on a flow network $G = (V, E)$ is at most $4|V|^2|E|$ for $|V| \ge 4$.
Each vertex has maximum height $2|V| - 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 $(2|V| - 1)(|V| - 2)$. A saturating push from $u$ to $v$ increases $\Phi$ by at most $v.h \le 2|V| - 1$, and there are at most $2|V||E|$ saturating pushes, so the total contribution over all saturating pushes to $\Phi$ is at most $(2|V| - 1)(2|V||E|)$. 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
$$(2|V| - 1)(|V| - 2) + (2|V| - 1)(2|V||E|) = 4|V|^2|E| + 2|V|^2 - 5|V| + 3 - 2|V||E|.$$
Using the fact that $|E| \ge |V| - 1$ and $|V| \ge 4$ we can bound the number of saturating pushes by $4|V|^2|E|$.