26.5 The relabel-to-front algorithm

26.5-1

Illustrate the execution of $\text{RELABEL-TO-FRONT}$ in the manner of Figure 26.10 for the flow network in Figure 26.1(a). Assume that the initial ordering of vertices in $L$ is $\langle v_1, v_2, v_3, v_4 \rangle$ and that the neighbor lists are

$$ \begin{aligned} v_1.N & = \langle s, v_2, v_3 \rangle, \\ v_2.N & = \langle s, v_1, v_3, v_4 \rangle, \\ v_3.N & = \langle v_1, v_2, v_4, t \rangle, \\ v_4.N & = \langle v_2, v_3, t \rangle. \end{aligned} $$

When we initialize the preflow, we have $29$ units of flow leaving $s$. Then, we consider $v_1$ since it is the first element in the $L$ list. When we discharge it, we increase it's height to $1$ so that it can dump $12$ of it's excess along its edge to vertex $v_3$, to discharge the rest of it, it has to increase it's height to $|V| + 1$ to discharge it back to $s$. It was already at the front, so, we consider $v_2$. We increase its height to $1$. Then, we send all of its excess along its edge to $v_4$. We move it to the front, which means we next consider $v_1$, and do nothing because it is not overflowing. Up next is vertex $v_3$. After increasing its height to $1$, it can send all of its excess to $t$. This puts $v_3$ at the front, and we consider the non-overflowing vertices $v_2$ and $v_1$. Then, we consider $v_4$, it increases its height to $1$, then sends $4$ units to $t$. Since it still has an excess of $9$ units, it increases its height once again. Then it becomes valid for it to send flow back to $v_2$ or to $v_3$. It considers $v_2$ first because of the ordering of its neighbor list. This means that $9$ units of flow are pushed back to $v_2$. Since $v_4.h$ increased, it moves to the front of the list Then, we consider $v_2$ since it is the only still overflowing vertex. We increase its height to $3$. Then, it is overflowing by $9$ so it increases its height to $3$ to send $9$ units to $v_4$. It's height increased so it goes to the of the list. Then, we consider $v_4$, which is overflowing. It pushes $7$ units to $v_3$. Since it is still overflowing by $2$, it increases its height to $4$ and pushes the rest back to $v_2$ and goes to the front of the list. Up next is $v_2$, which increases its height by $2$ to sends its overflow to $v_4$. The excess flow keeps bobbing around the four vertices, each time requiring them to increase their height a bit to discharge to a neighbor only to have that neighbor increase to discharge it back until $v_2$ has increased in height enough to send all of it's excess back to s. Last but not least, $v_3$ pushes its overflow of $7$ units to $t$, and gives us a maximum flow of $23$.

26.5-2 $\star$

We would like to implement a push-relabel algorithm in which we maintain a firstin, first-out queue of overflowing vertices. The algorithm repeatedly discharges the vertex at the head of the queue, and any vertices that were not overflowing before the discharge but are overflowing afterward are placed at the end of the queue. After the vertex at the head of the queue is discharged, it is removed. When the queue is empty, the algorithm terminates. Show how to implement this algorithm to compute a maximum flow in $O(V^3)$ time.

Initially, the vertices adjacent to $s$ are the only ones which are overflowing. The implementation is as follows:

PUSH-RELABEL-QUEUE(G, s)
    INITIALIZE-PREFLOW(G, s)
    let q be a new empty queue
    for v ∈ G.Adj[s]
        PUSH(q, v)
    while q.head != NIL
        DISCHARGE(q.head)
        POP(q)

Note that we need to modify the $\text{DISCHARGE}$ algorithm to push vertices $v$ onto the queue if $v$ was not overflowing before a discharge but is overflowing after one.

Between lines 7 and 8 of $\text{DISCHARGE}(u)$, add the line "if $v.e > 0$, $\text{PUSH}(q, v)$." This is an implementation of the generic push-relabel algorithm, so we know it is correct. The analysis of runtime is almost identical to that of Theorem 26.30. We just need to verify that there are at most $|V|$ calls to $\text{DISCHARGE}$ between two consecutive relabel operations. Observe that after calling $\text{PUSH}(u, v)$, Corollary 26.28 tells us that no admissible edges are entering $v$. Thus, once $v$ is put into the queue because of the push, it can't be added again until it has been relabeled. Thus, at most $|V|$ vertices are added to the queue between relabel operations.

26.5-3

Show that the generic algorithm still works if $\text{RELABEL}$ updates $u.h$ by simply computing $u.h = u.h + 1$. How would this change affect the analysis of $\text{RELABEL-TO-FRONT}$?

If we change relabel to just increment the value of $u$, we will not be ruining the correctness of the Algorithm. This is because since it only applies when $u.h \le v.h$, we won't be every creating a graph where $h$ ceases to be a height function, since $u.h$ will only ever be increasing by exactly $1$ whenever relabel is called, ensuring that $u.h + 1 \le v.h$. This means that Lemmatae 26.15 and 26.16 will still hold. Even Corollary 26.21 holds since all it counts on is that relabel causes some vertex's $h$ value to increase by at least $1$, it will still work when we have all of the operations causing it to increase by exactly $1$. However, Lemma 26.28 will no longer hold. That is, it may require more than a single relabel operation to cause an admissible edge to appear, if for example, $u.h$ was strictly less than the $h$ values of all its neighbors. However, this lemma is not used in the proof of Exercise 26.4-3, which bounds the number of relabel operations. Since the number of relabel operations still have the same bound, and we know that we can simulate the old relabel operation by doing (possibly many) of these new relabel operations, we have the same bound as in the original algorithm with this different relabel operation.

26.5-4 $\star$

Show that if we always discharge a highest overflowing vertex, we can make the push-relabel method run in $O(V^3)$ time.

We'll keep track of the heights of the overflowing vertices using an array and a series of doubly linked lists. In particular, let $A$ be an array of size $|V|$, and let $A[i]$ store a list of the elements of height $i$. Now we create another list $L$, which is a list of lists. The head points to the list containing the vertices of highest height. The next pointer of this list points to the next nonempty list stored in $A$, and so on. This allows for constant time insertion of a vertex into $A$, and also constant time access to an element of largest height, and because all lists are doubly linked, we can add and delete elements in constant time. Essentially, we are implementing the algorithm of Exercise 26.5-2, but with the queue replaced by a priority queue with constant time operations. As before, it will suffice to show that there are at most $|V|$ calls to discharge between consecutive relabel operations.

Consider what happens when a vertex $v$ is put into the priority queue. There must exist a vertex $u$ for which we have called $\text{PUSH}(u, v)$. After this, no ad- missible edge is entering $v$, so it can't be added to the priority queue again until after a relabel operation has occurred on $v$. Moreover, every call to $\text{DISCHARGE}$ terminates with a $\text{PUSH}$, so for every call to $\text{DISCHARGE}$ there is another vertex which can't be added until a relabel operation occurs. After $|V|$ $\text{DISCHARGE}$ operations and no relabel operations, there are no remaining valid $\text{PUSH}$ operations, so either the algorithm terminates, or there is a valid relabel operation which is performed. Thus, there are $O(V^3)$ calls to $\text{DISCHARGE}$. By carrying out the rest of the analysis of Theorem 26.30, we conclude that the runtime is $O(V^3)$.

26.5-5

Suppose that at some point in the execution of a push-relabel algorithm, there exists an integer $0 < k \le |V| - 1$ for which no vertex has $v.h = k$. Show that all vertices with $v.h > k$ are on the source side of a minimum cut. If such a $k$ exists, the gap heuristic updates every vertex $v \in V - \{s\}$ for which $v.h > k$, to set $v.h = \max(v.h, |V| + 1)$. Show that the resulting attribute $h$ is a height function. (The gap heuristic is crucial in making implementations of the push-relabel method perform well in practice.)

Suppose to try and obtain a contradiction that there were some minimum cut for which a vertex that had $v.h > k$ were on the sink side of that cut. For that minimum cut, there is a residual flow network for which that cut is saturated. Then, if there were any vertices that were also on the sink side of the cut which had an edge going to $v$ in this residual flow network, since it's $h$ value cannot be equal to $k$, we know that it must be greater than $k$ since it could be only at most one less than $v$. We can continue in this way to let $S$ be the set of vertices on the sink side of the graph which have an $h$ value greater than $k$. Suppose that there were some simple path from a vertex in $S$ to $s$. Then, at each of these steps, the height could only decrease by at most $1$, since it cannot get from above $k$ to $0$ without going through $k$, we know that there is no path in the residual flow network going from a vertex in $S$ to $s$. Since a minimal cut corresponds to disconnected parts of the residual graph for a maximum flow, and we know there is no path from $S$ to $s$, there is a minimum cut for which $S$ lies entirely on the source side of the cut. This was a contradiction to how we selected $v$, and so have shown the first claim.

Now we show that after updating the $h$ values as suggested, we are still left with a height function. Suppose we had an edge $(u, v)$ in the residual graph. We knew from before that $u.h \le v.h + 1$. However, this means that if $u.h > k$, so must be $v.h$. So, if both were above $k$, we would be making them equal, causing the inequality to still hold. Also, if just $v.k$ were above $k$, then we have not decreased it's $h$ value, meaning that the inequality also still must hold. Since we have not changed the value of $s.h$, and $t.h$, we have all the required properties to have a height function after modifying the $h$ values as described.