5.2.2.1. The Discharge Operation

The heart of the relabel-to-front algorithm is the following Discharge operation, which takes a single vertex \(x\) as its argument and ensures that \(e_x = 0\) at the time this operation returns. This procedure relies on a linked list \(\textrm{NBR}(x)\) and a pointer \(\textrm{CUR}(x)\) into this list. \(\textrm{NBR}(x)\) stores all neighbours of \(x\), that is, all vertices \(y\) such that \\(x,y)\) or \((y,x)\) is an edge of \(G\). The elements in this list are not stored in any particular order. \(\textrm{CUR}(x)\) is the next neighbour to which the operation tries to push excess flow from \(x\) if the edge \((x,y)\) is admissible.

PROCEDURE \(\boldsymbol{\textbf{Discharge}(G, u, f, h, x)}\):

---

INPUT:

• A directed graph \(G = (V, E)\)
• A capacity labelinng \(u : E \rightarrow \mathbb{R}^+\) of its edges
• A preflow \(f : E \rightarrow \mathbb{R}^+\)
• A height function \(h : V \rightarrow [0, 2n - 1]\)
• A vertex \(x \in V\)

OUTPUT:

• An updated preflow \(f' : E \rightarrow \mathbb{R}^+\) such that \(x\)'s excess \(e_x = 0\)
• An updated height function \(h' : V \rightarrow [0, 2n - 1]\)

---

1.     WHILE \(e_x > 0\) DO
2.         IF \(\textrm{CUR}(x) = \textrm{NULL}\) THEN
3.             \(\textrm{Relabel}(G, f, h, x)\)
4.             \(\textrm{CUR}(x) = \textrm{HEAD}(\textrm{NBR}(x))\)
5.         ELSIF the edge \((x, \textrm{CUR}(x))\) is admissible THEN
6.             \(\textrm{Push}(G, f, (x, \textrm{CUR}(x)))\)
7.         ELSE
8.             \(\textrm{CUR}(x) = \textrm{NEXT}(\textrm{CUR}(x))\)
9.     RETURN \((f, h)\)

The while-loop relabels \(x\) and pushes flow from \(x\) to its neighbours until \(x\)'s excess is zero.

Lines 5–8 hold no mystery: As long as \(e_x > 0\) and the current edge \((x, \textrm{CUR}(x))\) is admissible, the algorithm pushes excess from \(x\) to \(\textrm{CUR}(x)\) along this edge. If \((x, \textrm{CUR}(x))\) is not admissible, line 8 advances \(\textrm{CUR}(x)\) to the next neighbour \(y\) in the hope that the edge \((x, y)\) is admissible.

A more interesting aspect of the Discharge operation is that it relabels \(x\) and then resets \(\textrm{CUR}(x)\) to point to the head of \(\textrm{NBR}(x)\) if \(\textrm{CUR}(x) = \textrm{NULL}\), that is, once it has reached the end of the list of \(x\)'s neighbours. Since a Relabel operation is applicable only if none of x's out-edges is admissible, we need to prove that indeed \(x\) has no admissible out-edges once \(\textrm{CUR}(x) = \textrm{NULL}\). This follows immediately from the following invariant:

Invariant 5.24: There is no neighbour \(y\) of \(x\) that precedes \(\textrm{CUR}(x)\) in \(\textrm{NBR}(x)\) and such that the edge \((x, y)\) is admissible.

Proof: Initially, \(\textrm{CUR}(x) = \textrm{HEAD}(\textrm{NBR}(x))\), so the invariant holds. The invariant may be violated by changing \(\textrm{CUR}(x)\) or by creating admissible edges. First we prove that changing \(\textrm{CUR}(x)\) does not invalidate the invariant.

When we advance \(\textrm{CUR}(x)\) from some vertex \(y\) to its successor \(z \in \textrm{NBR}(x)\), then \(\textrm{CUR}(x)\) has the same predecessors in \(\textrm{NBR}(x)\) as before, plus \(y\). By the invariant, the edge \((x, w)\) is inadmissible for every predecessor \(w\) of \(y\) in \(\textrm{NBR}(x)\). Since advancing \(\textrm{CUR}(x)\) from \(y\) to \(z\) does not create any admissible edges, these edges remain inadmissible. The edge \((x, y)\) is inadmissible because this is the condition for advancing \(\textrm{CUR}(x)\) from \(y\) to \(z\) in line 8 of the Discharge procedure. Thus, the invariant continues to hold.

After setting \(\textrm{CUR}(x) = \textrm{HEAD}(\textrm{NBR}(x))\) in line 4 of the Discharge procedure, \(\textrm{CUR}(x)\) has no predecessors in \(\textrm{NBR}(x)\), so this cannot invalidate the invariant either.

Next consider the creation of admissible edges using Push Relabel operations.

By Lemma 5.25 below, a Push operation does not create any admissible edges. Thus, every edge \((x, w)\) such that \(w\) precedes \(\textrm{CUR}(x)\) in \(\textrm{NBR}(x)\) remains inadmissible after a Push operation.

By Lemma 5.26 below, all edges that become admissible as a result of a \(\boldsymbol{\textbf{Relabel}(w)}\) operation are out-edges of \(w\). Thus, if \(w \ne x\), all edges \((x, v)\) such that \(v\) precedes \(\textrm{CUR}(x)\) in \(\textrm{NBR}(x)\) remain inadmissible after any \(\boldsymbol{\textbf{Relabel}(w)}\) operation with \(w \ne x\).

A \(\boldsymbol{\textbf{Relabel}(x)}\) operation may create admissible out-edges of \(x\), but the only place in algorithm where this operation is called is in line 3 of a \(\boldsymbol{\textbf{Discharge}(x)}\) operation; line 4 then sets \(\textrm{CUR}(x) = \textrm{HEAD}(\textrm{NBR}(x))\), so there is no neighbour \(v\) of \(x\) that precedes \(\textrm{CUR}(x)\) in \(\textrm{NBR}(x)\) at all.

As we will see shortly, the relabel-to-front algorithm makes no changes to \(\textrm{CUR}(x)\), the preflow or the height function outside the Discharge procedure. Thus, the invariant is maintained at all times. ▨

Lemma 5.25: A Push operation does not create any admissible edges.

Proof: Consider an edge \((x, y)\) that is inadmissible, which means that \(h_x \ne h_y + 1\) or \(u^f_{x,y} = 0\).

A \(\boldsymbol{\textbf{Push}(w, z)}\) operation does not alter the height function \(h\). Thus, if \((x, y)\) is inadmissible because \(h_x \ne h_y + 1\), it remains inadmissible after the \(\textbf{Push}(w, z)\) operation.

If \(u^f_{x,y} = 0\) before the \(\boldsymbol{\textbf{Push}(w, z)}\) operation, then the edge remains inadmissible after the \(\boldsymbol{\textbf{Push}(w, z)}\) operation unless \(u^f_{x,y} > 0\) after the Push operation. This is possible only if \(x = z\) and \(y = w\) because \(u^f_{w,z}\) decreases as a result of a \(\boldsymbol{\textbf{Push}(w, z)}\) operation, \(u^f_{z,w}\) increases as a result of such an operation, and all other residual capacities remain unchanged. However, since we call \(\boldsymbol{\textbf{Push}(w, z)}\) only if the edge \((w, z)\) is admissible, that is, if \(h_w = h_z + 1\), this implies that \(h_x = h_y - 1\), that is, the edge \((x, y)\) remains inadmissible even if \(u^f_{x,y} > 0\) after the \(\boldsymbol{\textbf{Push}(w,z)}\) operation. ▨

Lemma 5.26: If an edge \((x, y)\) becomes admissible as a result of a \(\boldsymbol{\textbf{Relabel}(z)}\) operation, then \(x = z\). Moreover, \(z\) has no admissible in-edges after a \(\boldsymbol{\textbf{Relabel}(z)}\) operation.

Proof: Consider an edge \((x, y)\) that is inadmissible and such that \(x \ne z\). This means that \(h_x \ne h_y + 1\) or \(u^f_{x,y} = 0\). A \(\boldsymbol{\textbf{Relabel}(z)}\) operation does not alter the flow function \(f\) and thus neither the residual capacities of the edges. Thus, if \(u^f_{x,y} = 0\) before a \(\boldsymbol{\textbf{Relabel}(z)}\) operation, then \(u^f_{x,y} = 0\) after it, and the edge \((x, y)\) remains inadmissible.

If \(u^f_{x,y} > 0\), then \(h_x \ne h_y + 1\) before the Relabel operation. If \(y \ne z\), \(\boldsymbol{\textbf{Relabel}(z)}\) does not change \(h_x\) or \(h_y\) because we assumed above that \(x \ne z\), so the edge \((x, z)\) remains inadmissible.

If \(y = z\), then observe that before the \(\boldsymbol{\textbf{Relabel}(z)}\) operation, \(h_x \le h_y + 1\). This follows because the algorithm starts with a valid height function and Observations 5.11 and 5.14 show that Push and Relabel operations don't invalidate the height function. By Observation 5.13, a \(\boldsymbol{\textbf{Relabel}(z)}\) operation increases \(h_z = h_y\). Thus, \(h_x \le h_y\) after the \(\boldsymbol{\textbf{Relabel}(z)}\) operation, that is, the edge \((x, y)\) remains inadmissible. This finishes the proof that any inadmissible edge \((x,y)\) remains inadmissible after a \(\boldsymbol{\textrm{Relabel}(z)}\) operation unless \(x = z\).

Finally, consider an in-edge \((x, z)\) of \(z\). If this edge is admissible after relabelling \(z\), then \(h_x = h_z + 1\) after the \(\boldsymbol{\textbf{Relabel}(z)}\) operation and \(u^f_{x,z} > 0\) before and after the operation. By Observation 5.13, \(h_z\) increases as a result of relabelling \(z\). Thus, \(h_x > h_z + 1\) before the \(\boldsymbol{\textbf{Relabel}(z)}\) operation. By Observations 5.11 and 5.14, however, \(h\) is a valid height function at all times, that is, there exists no edge \((x,z)\) with \(u^f_{x,z} > 0\) and \(h_x > h_z + 1\) at any time during the algorithm. Thus, \(z\) has no admissible in-edge after relabelling \(z\). ▨

We have shown that Discharge operations apply Push and Relabel operations only when they are applicable. As we will see next, the relabel-to-front algorithm updates the flow and height function only via Discharge operations. Thus, it maintains a valid preflow and a valid height function.