6.8.3. Fixing Edges

In this section, we discuss how the repeated capacity scaling algorithm discovers "fixed" edges, edges for which we can guarantee that the difference between the node potentials of their endpoints are exactly the costs of these edges. We will then construct a modified graph \(G'\), one with an updated cost function. These fixed edges have the property that an optimal potential function for \(G'\) assigns exactly the same potential to their endpoints. Thus, we are justified in treating the endpoints of fixed edges as the same vertex, which we achieve by contracting fixed edges.

The first lemma in this section shows that if an edge \((x,y)\) carries a large amount of flow at any point during the \(\Delta\)-phase of the capacity scaling algorithm, then this edge will carry some non-negative amount of flow in the final minimum-cost flow computed by the algorithm. Thus, by Lemma 6.1, its reduced cost with respect to an optimal potential function \(\pi\) is \(c^\pi_{x,y} = 0\), that is, \(\pi_x\) and \(\pi_y\) differ by exactly \(c_{x,y}\); the edge becomes "fixed".

Lemma 6.46: If some edge \((x, y)\) carries \(f_{x,y} \ge 4\Delta n\) flow at some point during the \(\Delta\)-phase of the capacity scaling algorithm, then there exists a minimum-cost flow \(f'\) that satisfies \(f'_{x,y} > 0\).

Proof: Let \(f'\) be the minimum-cost flow obtained at the end of the capacity scaling algorithm. By Corollary 6.45, the total excess of all excess nodes is less than \(2\Delta' n\) during the \(\Delta'\)-phase, for any \(\Delta'\). Every augmentation during the \(\Delta'\)-phase decreases the excess of some excess node by \(\Delta'\), by sending \(\Delta'\) units of flow along some path in \(G_f\). Thus, the \(\Delta'\)-phase changes the flow along any edge in \(G\) by less than \(2\Delta' n\). This implies that \(f'_{x,y} \ge f_{x,y} - 2n(\Delta + \Delta/2 + \cdots + 1) > f_{x,y} - 4\Delta n = 0\). ▨

Corollary 6.47: If some edge \((x, y)\) carries \(f_{x, y} \ge 4\Delta\) flow at some point during the \(\Delta\)-phase of the capacity scaling algorithm, then \(c^\pi_{x,y} = 0\) for every optimal potential function \(\pi\).

Proof: By Lemma 6.46, there exists a minimum-cost flow \(f'\) such that \(f'_{x,y} > 0\). Since \(u_{x,y} = \infty\), we thus have \(0 < f'_{x,y} < u_{x,y}\). Since \(f'\) is a minimum-cost flow and \(\pi\) is an optimal potential function, Lemma 6.1 shows that \(c^\pi_{x,y} = 0\). ▨

Consider an edge \((x,y)\) that becomes fixed at some point during the execution of the algorithm, that is, an edge that is guaranteed to carry a non-zero amount of flow in the final minimum-cost flow computed by the algorithm because its current flow is \(f_{x,y} \ge 4\Delta\). We define a new flow network \(G'\) that is identical to \(G\) except that every edge \((w,z)\) has cost \(c'_{w,z} = c^\pi_{w,z}\), where \(\pi\) is the current potential function at the time when \((x,y)\) becomes fixed. The node supply balances are left unchanged: \(b'_z = b_z\) for all \(z \in V\).

This network \(G'\) is the one where we can contract the edge \((x,y)\) to obtain a smaller network on which to recurse. Specifically, we show that every optimal potential function \(\pi'\) for \(G'\) satisfies \(\pi'_x = \pi'_y\). Before proving this, we prove that we can recover an optimal potential function of \(G\)—which is what we really want to compute—from an optimal potential function of \(G'\).

Lemma 6.48: Let \(\pi\) be an arbitrary potential function, let \(G'\) be the network obtained from \(G\) by replacing the cost of every edge with its reduced cost \(c^\pi\), let \(f'\) be a minimum-cost flow in \(G'\), and let \(\pi'\) be an optimal potential function of \(G'\). Then \(f'\) is a minimum-cost flow in \(G\) and \(\pi' + \pi\) is an optimal potential function of \(G\).

Proof: Consider a minimum-cost flow \(f'\) and an optimal potential function \(\pi'\) of \(G'\). Since \(G\) and \(G'\) have the same edge capacities and node supply balances, \(f'\) is a feasible flow in \(G\). Moreover,

\[\begin{aligned} (c')^{\pi'}_{w,z} &= c'_{w,z} - \pi'_w + \pi'_z\\ &= c_{w,z} - \pi_w + \pi_z - \pi'_w + \pi'_z\\ &= c^{\pi'+\pi}_{w,z} \end{aligned}\]

for every edge \((w,z) \in G\).

By Lemma 6.2, we have \((c')^{\pi'}_{w,z} = c^{\pi'+\pi}_{w,z} \ge 0\) for every edge \((w,z) \in (G')^f = G^f\). Thus, by the same lemma, \(f'\) is a minimum-cost flow in \(G\) and \(\pi' + \pi\) is an optimal potential function for \(G\). ▨

Lemma 6.49: Let \(f\) be a pseudo-flow in \(G\), let \(\pi\) be a potential function such that every edge in \(G^f\) has non-negative reduced cost, let \(G'\) be the network obtained from \(G\) by replacing the cost of every edge with its reduced cost \(c^\pi\), and let \(\pi'\) be an optimal potential function for \(G'\). If \(f_{x,y} \ge 4\Delta\) for some edge \((x, y) \in G\), then \(\pi'_x = \pi'_y\).

Proof: Let

\[b''_z = \sum_{w \in V} (f_{z,w} - f_{w,z}) \quad \forall z \in V.\]

Let \(G''\) be the graph obtained from \(G\) by replacing the supply balance function \(b\) with \(b''\) and leaving all edge capacities and costs unchanged. Then \(f\) satisfies flow conservation in \(G''\). Since \(f\) is a pseudo-flow in \(G\), is is also a pseudo-flow in \(G''\). It is therefore a flow in \(G''\).

Since \((G'')^f = G^f\) (apart from different vertex excesses) and \(c^\pi_e \ge 0\) for every edge \(e \in G^f = (G'')^f\), Lemma 6.2 shows that \(f\) is a minimum-cost flow in \(G''\). Its proof also shows that \(\pi\) is an optimal potential function for \(G''\). Thus, by Corollary 6.47, \(c'_{x,y} = c^\pi_{x,y} = 0\).

Back to \(G'\). By Corollary 6.47, we have \((c')^{\pi'}_{x,y} = 0\), that is, \(c'_{x,y} = \pi'_x - \pi'_y\). Since \(c'_{x,y} = 0\), this shows that \(\pi'_x = \pi'_y\). ▨