6.3.4. Making Edge Costs Non-Negative

Some algorithms for computing minimum-cost flows assume that all edges have non-negative costs. The final transformation we discuss here shows how to satisfy this assumption. This transformation assumes that every edge has finite capacity, which we can ensure using the transformation in Section 6.3.2. Under this assumption, we can reduce the problem of computing a minimum-cost flow in \(G\) to computing a minimum-cost flow in the following network \(H\): Let \(E^-\) be the set of all edges of \(G\) with negative costs and let \(E^+ = E \setminus E^-\). Then \(H\) has the edge set \(E^+ \cup E^-_r\), where \(E^-_r = \{ (y, x) \mid (x, y) \in E^- \}\), that is, every negative-cost edge is reversed in \(H\). Every edge \((x, y) \in E^+\) has the same cost and capacity in \(H\) as in \(G\): \(u'_{x,y} = u_{x,y}\) and \(c'_{x,y} = c_{x,y}\). Every edge \((y, x) \in E^-_r\) has capacity \(u'_{y,x} = u_{x,y}\) and cost \(c'_{y,x} = -c_{x,y}\). Thus, every edge in \(H\) has non-negative cost. Finally, the node supplies in \(H\) are defined as

\[b'_y = b_y + \sum_{(x, y) \in E^-} u_{x,y} - \sum_{(y, z) \in E^-} u_{y,z}.\]

Intuitively, \(H\) is the residual network of \(G\) when saturating all negative-cost edges of \(G\): \(H = G^f\), where

\[f_{x,y} = \begin{cases} 0 & \text{if } c_{x,y} \ge 0\\ u_{x,y} & \text{if } c_{x,y} < 0. \end{cases}\]

The following lemma establishes a bijection between flows in \(G\) and \(H\). Its corollary shows that this implies that a minimum-cost flow in \(G\) can be obtained in a straightforward manner from a minimum-cost flow in \(H\).

Lemma 6.13: Consider two edge labellings \(f\) and \(f'\) of the edges in \(G\) and \(H\), respectively, such that

\[f'_{x,y} = \begin{cases} f_{x,y} & \text{if } (x, y) \in E^+\\ u_{y,x} - f_{y,x} & \text{if } (y, x) \in E^-. \end{cases}\]

Then \(f\) is a flow in \(G\) if and only if \(f'\) is a flow in \(H\).

Proof: First consider the flow conservation constraints. \(f\) satisfies these constraints in \(G\) if and only if

\[\begin{aligned} b_x &= \sum_{y \in V} \bigl(f_{x,y} - f_{y,x}\bigr)\\ &= \sum_{\substack{y \in V\\(x, y) \in E^+}} f_{x,y} + \sum_{\substack{y \in V\\(x, y) \in E^-}} f_{x,y} - \sum_{\substack{y \in V\\(y, x) \in E^+}} f_{y,x} - \sum_{\substack{y \in V\\(y, x) \in E^-}} f_{y,x}\\ &= \sum_{\substack{y \in V\\(x, y) \in E^+}} f'_{x,y} + \sum_{\substack{y \in V\\(y, x) \in E^-_r}} \bigl(u_{x,y} - f'_{y,x}\bigr) - \sum_{\substack{y \in V\\(y, x) \in E^+}} f'_{y,x} - \sum_{\substack{y \in V\\(x, y) \in E^-_r}} \bigl(u_{y,x} - f'_{x,y}\bigr)\\ &= \sum_{y \in V} \bigl(f'_{x,y} - f'_{y,x}\bigr) + \sum_{(x, y) \in E^-} u_{x,y} - \sum_{(y, x) \in E^-} u_{y,x}, \end{aligned}\]

which is true if and only if

\[b_x - \sum_{(x, y) \in E^-} u_{x,y} + \sum_{(y, x) \in E^-} u_{y,x} = \sum_{y \in V} \bigl(f'_{x,y} - f'_{y,x}\bigr),\]

that is, if and only if

\[b'_x = \sum_{y \in V} \bigl(f'_{x,y} - f'_{y,x}\bigr).\]

Thus, \(f\) satisfies the flow conservations constraints in \(G\) if and only if \(f'\) does in \(H\).

Next consider the capacity constraints. \(f\) satisfies the capacity constraints in \(G\) if and only if, for every edge \((x, y) \in G\),

\[0 \le f_{x,y} \le u_{x,y}.\]

If \((x,y) \in E^+\), then this is true if and only if \(0 \le f'_{x,y} \le u'_{x,y}\) because \(f'_{x,y} = f_{x,y}\) and \(u'_{x,y} = u_{x,y}\).

If \((x, y) \in E^-\), then \((y, x) \in E^-_r\), \(u'_{y,x} = u_{x,y}\), and \(f'_{y,x} = u_{x,y} - f_{x,y}\). Thus, \(0 \le f_{x,y} \le u_{x,y}\) if and only if \(0 \le u_{x,y} - f_{x,y} \le u_{x,y}\), that is, if and only if \(0 \le f'_{y,x} \le u'_{y,x}\).

This shows that \(f\) satisfies the capacity constraints in \(G\) if and only if \(f'\) satisfies the capacity constraints in \(H\). ▨

Corollary 6.14: For two flows \(f\) and \(f'\) as in Lemma 6.13, \(f\) is a minimum-cost flow in \(G\) if and only if \(f'\) is a minimum-cost flow in \(H\).

Proof: Consider two flows \(f^{(1)}\) and \(f^{(2)}\) in \(G\) and their corresponding flows \(g^{(1)}\) and \(g^{(2)}\) in \(H\) as defined in Lemma 6.13. For \(i \in \{1, 2\}\), the cost of \(f^{(i)}\) is \(\sum_{e \in E} c_ef^{(i)}_e\). The cost of \(g^{(i)}\) is

\[\begin{aligned} \sum_{(x, y) \in E^+} c'_{x,y} g^{(i)}_{x,y} + \sum_{(y, x) \in E^-_r} c'_{y,x} g^{(i)}_{y,x} &= \sum_{(x, y) \in E^+} c_{x,y} f^{(i)}_{x,y} - \sum_{(x, y) \in E^-} c_{x,y} \Bigl(u_{x,y} - f^{(i)}_{x,y}\Bigr)\\ &= \sum_{e \in E} c_ef^{(i)}_e - \sum_{e \in E^-} c_eu_e. \end{aligned}\]

Thus, the cost of \(g^{(i)}\) is exactly \(\sum_{e \in E^-} c_eu_e\) lower than the cost of \(f^{(i)}\). Therefore, \(f^{(1)}\) has a lower cost than \(f^{(2)}\) if and only if \(g^{(1)}\) has a lower cost than \(g^{(2)}\), that is, the transformation in Lemma 6.13 establishes a bijection between the minimum-cost flows in \(G\) and \(H\). ▨