6.1.2. The Residual Network and Reduced Costs

The second characterization of a minimum-cost flow uses the reduced costs of edges in the residual network \(G^f\) to decide whether \(f\) is a minimum-cost flow. This network is defined as in Chapter 5, with the added twist that edges in \(G^f\) now have residual costs and the definition of the excess of a vertex is based on the supply balance the vertex started out with in \(G\):

Let \(G = (V, E)\) be a network with vertex supply balances \(b: V \rightarrow \mathbb{R}\), edge capacities \(u : E \rightarrow \mathbb{R}^+\), and edge costs \(c : E \rightarrow \mathbb{R}\), and let \(f : E \rightarrow \mathbb{R}^+\) be a pseudo-flow in \(G\). The residual network of \(G\) with respect to \(f\) is the graph \(G^f = \bigl(V, E^f\bigr)\) with edge set

\[E^f = \{(x, y) \mid (x, y) \in G \text{ and } f_{x,y} < u_{x,y}\} \cup \{(x, y) \mid (y, x) \in G \text{ and } f_{y,x} > 0\}.\]

The residual capacity of an edge \((x, y) \in G^f\) is

\[u^f_{x,y} = u_{x,y} - f_{x,y} + f_{y,x}.\]

The residual cost of an edge \((x, y) \in G^f\) is

\[c^f_{x,y} = \begin{cases} c_{x,y} & \text{if } (x, y) \in G\\ -c_{y,x} & \text{if } (y, x) \in G. \end{cases}\]

The excess (residual supply balance) of a vertex \(x \in V\) is

\[e_x = b_x + \sum_{y \in V} (f_{y,x} - f_{x,y}).\]

We say that a vertex \(x\) is an excess vertex if its excess is positive; \(x\) is a deficit vertex if its excess is negative.

Note that the definition of \(G^f\) and of the residual capacities is identical to the one used in Chapter 5. The definition of the excess of a vertex \(x\) is the same as in Chapter 5, except that we add \(b_x\) to the excess. The definition of the residual cost of an edge has no counterpart in Chapter 5 because there are no edge costs in the maximum flow problem.

One technical difficulty with the construction of \(G^f\) above arises when \(G\) contains both edges \((x, y)\) and \((y, x)\) for two vertices \(x\) and \(y\). In this case, if \((x, y) \in G^f\), we require both that \(c^f_{x,y} = c_{x,y}\) and \(c^f_{x,y} = -c_{y,x}\), which is possible only if \(c_{x,y} = -c_{y,x}\), a condition that may not be satisfied by the input network \(G\). In implementations of the minimum-cost flow algorithms discussed in this chapter, it is easy to sidestep this issue by allowing \(G^f\) to have two copies of the edge \((x, y)\), one representing the edge \((x, y) \in G\) and therefore with cost \(c^f_{x,y} = c_{x,y}\), the other representing the reversal of the edge \((y, x) \in G\) and therefore with cost \(c^f_{x,y} = -c_{y,x}\). In the discussion of the algorithms in this chapter, on the other hand, it is awkward to distinguish between these two edges from \(x\) to \(y\) in \(G^f\). Therefore, we assume that the graph \(G\) contains at most one of the edges \((x, y)\) and \((y, x)\), for every pair of vertices \(x, y \in G\).

If the input graph \(G\) does not satisfy this assumption, we can construct a graph \(G'\) satisfying this assumption by considering every pair of vertices \(x, y \in G\) such that \(G\) contains both edges \((x, y)\) and \((y, x)\) and replacing one of these edges, say \((x, y)\), by two edges \((x, z)\) and \((z, y)\), where \(z\) is a new vertex with supply balance \(b_z = 0\). We set \(u_{x,z} = u_{z,y} = u_{x,y}\), \(c_{x,z} = c_{x,y}\), and \(c_{z,y} = 0\).

Exercise 6.2: Prove that there exists a one-to-one correspondence between feasible flows in \(G\) and in \(G'\), and that any two such flows have the same cost.

Thus, we can find a minimum-cost flow in \(G\) by computing a minimum-cost flow in \(G'\) instead, and \(G'\) satisfies our assumption that there are no two vertices \(x, y \in G'\) such that \(G'\) contains both edges \((x, y)\) and \((y, x)\).

We are now ready to state our next characterization of minimum-cost flows.

Lemma 6.2: A flow \(f\) is a minimum-cost flow if and only if there exists a potential function \(\pi\) such that every edge \((x, y)\) in \(G^f\) has reduced cost \(c^\pi_{x,y} \ge 0\), where the reduced cost of an edge \((x, y)\) is defined as

\[c^\pi_{x,y} = c^f_{x,y} - \pi_x + \pi_y.\]

Proof: First let \(f\) be a minimum-cost flow and let \(\pi\) be an optimal potential function.

Every edge \((x, y) \in G^f\) that is also an edge of \(G\) satisfies \(f_{x,y} < u_{x,y}\). Thus, by the second condition in Lemma 6.1, \(c^\pi_{x,y} \ge 0\).

If \((x, y)\) is not an edge of \(G\), then \((y, x)\) is an edge of \(G\) and \(f_{y,x} > 0\). Thus, by the first condition in Lemma 6.1, \(c^\pi_{y,x} \le 0\). Since \(c^\pi_{x,y} = -c^\pi_{y,x}\), this shows that \(c^\pi_{x,y} \ge 0\) also in this case, that is, the "only if" direction of the lemma holds.

To prove the "if" direction, let \(f\) be a flow and let \(\pi\) be a potential function such that every edge in \(G^f\) satisfies \(c^\pi_{x,y} \ge 0\). Let \((x, y)\) be an edge of \(G\). If \(f_{x,y} > 0\), then \((y, x) \in G^f\), so \(c^\pi_{y,x} \ge 0\) and, therefore, \(c^\pi_{x,y} \le 0\). Thus, \(f\) and \(\pi\) satisfy the first condition in Lemma 6.1.

If \(f_{x,y} < u_{x,y}\), then \((x, y) \in G^f\), so \(c^\pi_{x,y} \ge 0\). Thus, \(f\) and \(\pi\) satisfy the second condition in Lemma 6.1. Since \(f\) and \(\pi\) satisfy both conditions in Lemma 6.1, \(f\) is a minimum-cost flow in \(G\). ▨