6.8.1. From Potential Function to Flow

In this section, we prove how to compute a minimum-cost flow \(f\) from an optimal potential function \(\pi\) by formulating it as a maximum flow problem. This allows us to focus on computing an optimal potential function in the remainder of the discussion of the repeated capacity scaling algorithm.

Lemma 6.43: Let \(\pi\) be an optimal potential function for an uncapacitated flow network \(G\). Then a minimum-cost flow in \(G\) can be computed in \(O\bigl(n^2 \sqrt{m}\bigr)\) time.

Proof: By Lemma 6.1, every minimum-cost flow in \(G\) satisfies \(f_{x,y} = 0\) if \(c^\pi_{x,y} > 0\) and \(f_{x,y} = u_{x,y}\) if \(c^\pi_{x,y} < 0\) for every edge \((x, y) \in G\). Since \(u_{x,y} = \infty\) for every edge \((x, y) \in G\), the case when \(f_{x,y} = u_{x,y}\) is impossible, so all edges in \(G\) satisfy \(c^\pi_{x,y} \ge 0\).

We start by setting \(f_{x,y} = 0\) for every edge \((x,y)\) that satisfies \(c^\pi_{x,y} > 0\), which is equivalent to removing these edges from \(G\). Let \(G'\) be the resulting graph.

Now let \(f'\) be an arbitrary flow in \(G'\). By setting

\[f_{x,y} = \begin{cases} f'_{x,y} & \text{if } (x,y) \in G'\\ 0 & \text{if } (x,y) \notin G', \end{cases}\]

we obtain a feasible flow in \(G\).

Since every edge \((x,y)\) in \(G'\) satisfies \(c^\pi_{x,y} = 0\), \(f\) and \(\pi\) satisfy the complementary slackness conditions of Lemma 6.1, that is, \(f\) is a minimum-cost flow in \(G\).

To find a flow \(f'\) in \(G'\), we use the construction from Section 6.4.1, which reduces the problem to a maximum flow problem. Using the highest vertex preflow-push algorithm, we can thus find the flow \(f'\) in \(O\bigl(n^2\sqrt{m}\bigr)\) time. ▨