5.2.2.3. Running Time Analysis

Next, let us prove that the algorithm runs in \(O\bigl(n^3\bigr)\) time, as claimed at the beginning of Section 5.2.2. We start by proving that the algorithm performs at most \(O\bigl(n^3\bigr)\) Discharge operations. Since each iteration of the while-loop in the RelabelToFront executes one Discharge operation, this implies that this while-loop runs for at most \(O\bigl(n^3\bigr)\) iterations.

Lemma 5.27: The relabel-to-front algorithm calls Discharge \(O\bigl(n^3\bigr)\) times.

Proof: Let us divide the sequence of calls to the Discharge procedure into phases. The last \(\boldsymbol{\textbf{Discharge}(x)}\) operation in each phase relabels \(x\). All other Discharge operations in a phase do not relabel any vertex. The Discharge operations in the last phase do not relabel any vertex.

Each phase consists of at most \(n\) calls to Discharge. Indeed, no \(\boldsymbol{\textbf{Discharge}(x)}\) operation in this phase, except possibly the last, relabels \(x\). Thus, the vertex \(x\) discharged by this operation is not moved to the front of \(L\) after the \(\boldsymbol{\textbf{Discharge}(x)}\) operation finishes and the distance of the current vertex \(x\) from the head of the list \(L\) increases after each call to \(\boldsymbol{\textbf{Discharge}(x)}\). This can happen at most \(n - 1\) times before \(x = \textrm{NULL}\).

Since the relabel-to-front algorithm is a variant of the generic preflow-push algorithm, Lemma 5.20 shows that the algorithm performs at most \(2n(n-1)\) Relabel operations. Since the last Discharge operation in each phase except the last relabels its argument, this implies that the sequence of calls to Discharge has at most \(2n(n-1) + 1 < 2n^2\) phases. Since each such phase consists of at most \(n\) calls to Discharge, this shows that there are less than \(2n^3\) calls to Discharge. ▨

Using this lemma, we can immediately bound the running time of the relabel-to-front algorithm.

Lemma 5.28: The running time of the relabel-to-front algorithm is \(O\bigl(n^3\bigr)\).

Proof: Excluding the work performed by Discharge operations, the RelabelToFront procedure takes \(O\bigl(n^3\bigr)\) time. Indeed, lines 1–3 take \(O(n)\) time, lines 4–9 take \(O(m) = O\bigl(n^2\bigr)\) time, and each iteration of the while-loop in lines 10–15 takes constant time (excluding the cost of Discharge). Since each iteration of the while-loop performs one Discharge operation, Lemma 5.27 shows that the while-loop runs for \(O\bigl(n^3\bigr)\) iteration, so the cost of lines 10–15 excluding Discharge operations is \(O\bigl(n^3\bigr)\).

A Discharge operation spends all its time in the while-loop in lines 1–8. Each iteration performs one of three actions, so it suffices to bound the total cost of each action summed over all iterations of the while-loop for all vertices.

The first possibility is that the current vertex \(x\) is relabelled in line 3, followed by resetting \(\textrm{CUR}(x)\) to the head of \(\textrm{NBR}(x)\) in line 4. By Exercise 5.2, this takes \(O(n)\) time. By Lemma 5.20, the total number of Relabel operations any preflow-push algorithm performs is \(O\bigl(n^2\bigr)\). Thus, the total cost of lines 3–4 summed over all invocations of Discharge is \(O\bigl(n^3\bigr)\).

The second possible action is to push flow along the current edge \((x, \textrm{CUR}(x))\). By Exercise 5.2, this takes constant time. By Lemma 5.21, there are only \(O(nm) = O\bigl(n^3\bigr)\) saturating Push operations in total. By Observation 5.12, we have \(e_x = 0\) after a non-saturating Push operation, so the Discharge operation returns and we can have at most one non-saturating Push operation per invocation of Discharge. Since Discharge is called \(O\bigl(n^3\bigr)\) times, by Lemma 5.27, this shows that the algorithm performs \(O\bigl(n^3\bigr)\) non-saturating Push operations. The total number of Push operations summed over all invocations of Discharge is thus \(O\bigl(n^3\bigr)\), and the total cost of line 6 summed over all invocations of Discharge is \(O\bigl(n^3\bigr)\).

Finally, consider the cost of line 8. Note that each invocation of line 8 moves \(\textrm{CUR}(x)\) one step closer to the end of \(\textrm{NBR}(x)\). Since \(\textrm{NBR}(x)\) has length at most \(n\), this can happen at most \(n\) times between two consecutive \(\boldsymbol{\textbf{Relabel}(x)}\) operations. Since Lemma 5.20 shows that there are only \(O\bigl(n^2\bigr)\) Relabel operations in total, the cost of line 8 for all invocations of Discharge is thus \(O\bigl(n^3\bigr)\). ▨