6.3.1. Making the Network Strongly Connected
An assumption that simplifies many minimum-cost flow algorithms is that there should exist an uncapacitated path between every pair of vertices. To satisfy this assumption, we add two new vertices \(s\) and \(t\) to \(G\) along with uncapacitated edges \((s, t)\), \((x, s)\), and \((t, x)\) for every vertex \(x \in V\).1 Each of these edges has cost \(\sum_{e \in E} |c_e| + 1\), where \(E\) is the set of edges in \(G\) before adding these new edges.2 Let \(H\) be the resulting supergraph of \(G\). Clearly, there exists an uncapacitated path between every pair of vertices in \(H\). The next lemma shows that \(G\) and \(H\) have the same minimum-cost flow.
Lemma 6.9: Every minimum-cost flow in \(G\) is also a minimum-cost flow in \(H\) and vice versa.
Proof: We prove that a flow \(f'\) in \(H\) is a minimum-cost flow only if \(f'_{x,y} = 0\) for every edge \((x, y) \notin G\). Thus, every minimum-cost flow in \(H\) is a flow in \(G\) and every minimum-cost flow in \(G\) is trivially a flow in \(H\). The lemma follows.
So consider any flow \(f'\) in \(H\) such that \(f'_{x,y} > 0\) for at least one edge \((x, y) \notin G\). We prove that \(H^{f'}\) has a negative-cost cycle, which implies that \(f'\) is not a minimum-cost flow in \(H\), by Lemma 6.3.
Let \(f\) be a minimum-cost flow in \(G\) and let \(\delta\) be defined as
\[\delta_{x,y} = \max\bigl(0, f_{x,y} - f_{y,x} - f'_{x,y} + f'_{y,x}\bigr).\]
By Lemma 6.6, \(\delta\) is a circulation in \(H^{f'}\). Moreover, since \(f_{x,y} = f_{y,x} = 0\) and \(f'_{y,x} = 0\) for every edge \((x, y)\) of \(H\) that is not an edge of \(G\), we have \(\delta_{x,y} = 0\) and \(\delta_{y,x} = f'_{x,y}\) for each such edge \((x, y)\).
By Lemma 6.5, \(\delta\) is a sum of cycle flows \(\delta^{(1)}, \ldots, \delta^{(t)}\) in \(H^{f'}\). Since \(f'_{x,y} > 0\) for some edge \((x, y) \notin G\), its reverse \((y, x)\) satisfies \(\delta_{y,x} > 0\). Thus, there exists a cycle flow \(\delta^{(i)}\) such that \(\delta^{(i)}_{y,x} > 0\).
For every edge \((w,z) \in H\) and every cycle flow \(\delta^{(j)}\), we have \(\delta^{(j)}_{w,z} \ge 0\) because \(\delta^{(j)}\) is a pseudo-flow. Since \(\sum_{j=1}^t \delta^{(j)}_{w,z} = \delta_{w,z}\), this implies that \(\delta^{(j)}_{w,z} \le \delta_{w,z}\) for every cycle flow \(\delta^{(j)}\). Since \(\delta_{w,z} = 0\) for every edge \((w,z)\) of \(H\) that is not in \(G\), this implies that \(\delta^{(i)}_{w,z} = 0\) for every such edge. Thus, \(\delta^{(i)}\) uses only edges \((w,z)\) such that \((w,z) \in G\) or \((z,w)\) is an edge of \(H\) that is not in \(G\).
Since \(\delta^{(i)}\) uses at least one edge of the latter type, namely \((y, x)\), the cost of the cycle \(C\) used by \(\delta^{(i)}\) is at most \(\sum_{e \in G} |c_e| - \sum_{e \in G} |c_e| - 1 < 0\). The first sum is an upper bound on the total cost of all edges in \(G\) and the remainder of the expression is the cost of \((y, x)\). Thus, \(C\) is a negative-cost cycle in \(H^{f'}\). ▨
In an actual implementation, it would be sufficient to choose an arbitrary vertex \(s \in V\) and add uncapacitated edges \((s, x)\) and \((x, s)\) for every vertex \(x \in V \setminus \{s\}\). However, this creates pairs of parallel edges, a situation we chose to avoid in this chapter.
This is very similar to the construction we applied in the proof of Lemma 6.3. In that proof, we added edges to \(G^f\) to ensure that every vertex is reachable from \(s\) and we chose the edge weights so that the addition of these edges does not create any negative-cost cycles.
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.