6.2.3. Flows and Circulations in the Residual Network

The next two lemmas establish essentially that we can arrive at a flow in \(G\) by starting with any pseudo-flow \(f\) (e.g., \(f_e = 0\) for all \(e \in G\)) and then repeatedly augmenting it with a flow in the residual network \(G^f\). They show that the difference between two pseudo-flows in a network is a pseudo-flow in the residual network of one of the two flows.

Lemma 6.6: For two pseudo-flows \(f\) and \(f'\) in \(G\), the edge labelling \(\delta\) defined as

\[\delta_{x,y} = \max\bigl(0, f'_{x,y} - f'_{y,x} - f_{x,y} + f_{y,x}\bigr)\]

is a pseudo-flow in \(G^f\). If \(f'\) is a flow, then so is \(\delta\). If both \(f\) and \(f'\) are flows, then \(\delta\) is a circulation.

Proof: First we prove that \(\delta\) is a pseudo-flow in \(G^f\). By definition, \(\delta_{x,y} \ge 0\) for every edge \((x, y) \in G^f\). Since \(f\) is a pseudo-flow, we have \(f_{x,y} \le u_{x,y}\) and \(f_{y,x} \ge 0\) for every edge \((x, y) \in G^f\). Thus,

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

If \(\delta_{x,y} = 0\), this implies that \(\delta_{x,y} \le u^f_{x,y}\). If \(\delta_{x,y} > 0\), then

\[\begin{aligned} \delta_{x,y} &= f'_{x,y} - f'_{y,x} - f_{x,y} + f_{y,x}\\ &\le f'_{x,y} - f_{x,y} + f_{y,x}\\ &\le u_{x,y} - f_{x,y} + f_{y,x}\\ &= u^f_{x,y} \end{aligned}\]

because \(f'\) is a pseudo-flow and thus \(f'_{y,x} \ge 0\) and \(f'_{x,y} \le u_{x,y}\). This proves that \(\delta\) is a pseudo-flow in \(G^f\).

To prove that \(\delta\) is a flow if \(f'\) is a flow, let \(\delta'_{x,y} = f'_{x,y} - f_{x,y}\). Then \(\delta_{x,y} = \max\bigl(0, \delta'_{x,y} - \delta'_{y,x}\bigr)\) for every edge \((x, y) \in G^f\). Thus, for all \(x \in V\),

\begin{align} \sum_{y \in V} \Bigl(\delta_{x,y} - \delta_{y,x}\Bigr) &= \sum_{y \in V} \biggl(\max\Bigl(0, \delta'_{x,y} - \delta'_{y,x}\Bigr) - \max\Bigl(0, \delta'_{y,x} - \delta'_{x,y}\Bigr)\biggr)\\ &= \sum_{y \in V} \Bigl(\delta'_{x,y} - \delta'_{y,x}\Bigr)\\ &= \sum_{y \in V} \biggl(\Bigl(f'_{x,y} - f_{x,y}\Bigr) - \Bigl(f'_{y,x} - f_{y,x}\Bigr)\biggr)\\ &= \sum_{y \in V} \Bigl(f'_{x,y} - f'_{y,x}\Bigr) - \sum_{y \in V} \Bigl(f_{x,y} - f_{y,x}\Bigr)\\ &= b_x - \sum_{y \in V} \Bigl(f_{x,y} - f_{y,x}\Bigr)\tag{6.8}\\ &= e_x. \end{align}

(6.8) follows because \(f'\) is a flow, that is, it satisfies the flow conservation constraints in \(G\). Thus, \(\delta\) satisfies the flow conservation constraints in \(G^f\) and, being a pseudo-flow in \(G^f\), is a flow in \(G^f\).

Finally, assume that both \(f\) and \(f'\) are flows in \(G\). By the above argument, \(\delta\) is a flow in \(G^f\). Since \(f\) is a flow, \(e_x = 0\) for all \(x \in V\), which implies that

\[\sum_{y \in V} \bigl(\delta_{x,y} - \delta_{y,x}\bigr) = e_x = 0 \quad \forall x \in V,\]

that is, \(\delta\) is a circulation. ▨

Lemma 6.7: If \(f\) is a pseudo-flow in \(G\) and \(\delta\) is a pseudo-flow in \(G^f\), then the edge labelling \(f'\) defined as

\[f'_{x,y} = f_{x,y} + \delta_{x,y} - \delta_{y,x} \quad \forall (x, y) \in G\]

is a pseudo-flow in \(G\) of cost

\[\sum_{e \in G} c_ef_e + \sum_{e \in G^f} c^f_e\delta_e.\]

If \(f\) is a flow and \(\delta\) is a circulation, then \(f'\) is a flow.

Proof: First we prove that \(f'\) is a pseudo-flow in \(G\).

Consider any edge \((x,y) \in G\). Since \((x,y) \in G\), we have \((y,x) \notin G\), that is, \(f_{y,x} = u_{y,x} = 0\). Since \(\delta\) is a pseudo-flow in \(G^f\), we have

\[0 \le \delta_{x,y} \le u^f_{x,y} = u_{x,y} - f_{x,y}\]

and

\[0 \le \delta_{y,x} \le u^f_{y,x} = f_{x,y}.\]

Thus,

\[f'_{x,y} \le f_{x,y} + u_{x,y} - f_{x,y} = u_{x,y}\]

and

\[f'_{x,y} \ge f_{x,y} - f_{x,y} = 0.\]

This proves that \(f'\) is a pseudo-flow.

Next assume that \(f\) is a flow and \(\delta\) is a circulation. Then

\[\begin{aligned} \sum_{(x,y) \in G}f'_{x,y} - \sum_{(y,x) \in G} f'_{y,x} &= \sum_{(x,y) \in G} \bigl(f_{x,y} + \delta_{x,y} - \delta_{y,x}\bigr) - \sum_{(y,x) \in G} \bigr(f_{y,x} + \delta_{y,x} - \delta_{x,y}\bigr)\\ &= \sum_{(x,y) \in G} f_{x,y} - \sum_{(y,x) \in G} f_{y,x} + \sum_{(x,y) \in G} \bigl(\delta_{x,y} - \delta_{y,x}\bigr) + \sum_{(y,x) \in G} \bigl(\delta_{x,y} - \delta_{y,x}\bigr)\\ &= b_x. \end{aligned}\]

Thus, \(f'\) satisfies the flow conservation constraints. Being a pseudo-flow, it is therefore a flow.

Finally, consider the cost of \(f'\). Since \(c^f_{x,y} = c_{x,y}\) and \(c^f_{y,x} = -c_{x,y}\) for every edge \((x,y) \in G\), we have

\[\begin{aligned} \sum_{(x,y) \in G} c_{x,y} f'_{x,y} &= \sum_{(x,y) \in G} c_{x,y}f_{x,y} + \sum_{(x,y) \in G} c_{x,y}\delta_{x,y} - \sum_{(x,y) \in G} c_{x,y}\delta_{y,x}\\ &= \sum_{(x,y) \in G} c_{x,y} f_{x,y} + \sum_{(x,y) \in G} c^f_{x,y}\delta_{x,y} + \sum_{(x,y) \in G} c^f_{y,x}\delta_{y,x}\\ &= \sum_{e \in G} c_ef_e + \sum_{e \in G^f} c^f_e\delta_e.\ \text{▨} \end{aligned}\]

The final lemma in this section will be used in the correctness proof of the enhanced capacity scaling algorithm in Section 6.9. Intuitively, this lemma says that a pseudo-flow \(\delta\) in the residual network \(G^f\) of a pseudo-flow \(f\) can be reversed (sending flow from \(y\) to \(x\) if \(\delta\) sends flow from \(x\) to \(y\)) to obtain a pseudo-flow \(\delta^r\) in the residual network \(G^{f'}\) of another pseudo-flow \(f'\) provided that \(\delta\) is "bounded by the difference between \(f'\) and \(f\)".

Lemma 6.8: Let \(f\) and \(f'\) be pseudo-flows in \(G\) and let \(\delta\) be a pseudo-flow in \(G^f\) such that

\[\delta_{x,y} \le \max\Bigl(0, \bigl(f'_{x,y} - f'_{y,x}\bigr) - \bigl(f_{x,y} - f_{y,x}\bigr)\Bigr) \quad \forall (x, y) \in G^f.\]

Then the function \(\delta^r\) defined as \(\delta^r_{x,y} = \delta_{y,x}\) is a pseudo-flow in \(G^{f'}\). If \(\delta\) is a circulation, cycle flow or path flow, then so is \(\delta^r\).

Proof: As in the proof of Lemma 6.6, let \(\delta'_{x,y} = f'_{x,y} - f_{x,y}\). Then \(0 \le \delta_{x,y} \le \max\bigl(0, \delta'_{x,y} - \delta'_{y,x}\bigr)\). Thus, since \(\delta^r_{y,x} = \delta_{x,y}\), \(\delta^r\) is a pseudo-flow in \(G^{f'}\) if \(\max\bigl(0, \delta'_{x,y} - \delta'_{y,x}\bigr) \le u^{f'}_{y,x}\) for every edge \((y, x) \in G^{f'}\).

If \(\delta'_{x,y} - \delta'_{y,x} < 0\), then \(\max\bigl(0, \delta'_{x,y} - \delta'_{y,x}\bigr) = 0 \le u^{f'}_{y,x}\) because \(f'\) is a pseudo-flow in \(G\) and thus \(u^{f'}_{y,x} \ge 0\).

If \(\delta'_{x,y} - \delta'_{y,x} \ge 0\), then \(\max\bigl(0, \delta'_{x,y} - \delta'_{y,x}\bigr) = \delta'_{x,y} - \delta'_{y,x}\). In this case,

\[\begin{aligned} u^{f'}_{y,x} &= u_{y,x} - f'_{y,x} + f'_{x,y}\\ &= u_{y,x} - f_{y,x} + f_{x,y} - \bigl(f'_{y,x} - f_{y,x}\bigr) + \bigl(f'_{x,y} - f_{x,y}\bigr)\\ &= u^f_{y,x} - \delta'_{y,x} + \delta'_{x,y}\\ &\ge \delta'_{x,y} - \delta'_{y,x} \end{aligned}\]

because \(f\) is a pseudo-flow and thus \(u^f_{y,x} \ge 0\). This proves that \(\delta^r\) is a pseudo-flow in \(G_{f'}\).

The claim that \(\delta^r\) is a circulation, cycle flow or path flow if \(\delta\) is is straightforward to verify because \(\delta^r\) uses the same edges as \(\delta\), only in the opposite directions. ▨