6.2.2. Decomposition into Cycles and Paths

In this section, we prove that every flow can be written as a sum of a bounded number of cycle flows and path flows. To prove this, we need the following lemma, which states that, as long as there exist supply and demand vertices, every flow sends a positive amount of flow along some path from a supply vertex to a demand vertex:

Lemma 6.4: If \(f\) is a flow in a network \(G\) and \(b_x \ne 0\) for some vertex \(x \in G\), then there exists a path \(P\) in \(G\) from a supply vertex to a demand vertex such that \(f_e > 0\) for every edge \(e \in P\).

Proof: Since \(\sum_{x \in V} b_x = 0\), the existence of a supply vertex implies that there must exist a demand vertex and vice versa. Thus, if there exists a vertex \(x\) with \(b_x \ne 0\), we can choose \(x\) to be a supply vertex. Let \(R\) be the set of vertices reachable from \(x\) in the subgraph \(G^+ = (V, E^+)\), where \(E^+ = \{ e \in E \mid f_e > 0 \}\) is the set of edges in \(G\) used by \(f\). If \(R\) contains a demand vertex \(y\), then there exists a path \(P\) from \(x\) to \(y\) consisting of only edges in \(E^+\) and the lemma holds. If \(R\) contains no demand vertex, then \(R\) is a cut of \(G\) because \(x \in R\) and \(G\) has at least one demand vertex, which must be in \(V \setminus R\). Since \(x \in R\), \(b_x > 0\), and \(b_y \ge 0\) for all \(y \in R\), we have

\begin{align} 0 &< \sum_{y \in R} b_y\\ &= \sum_{y \in R} \sum_{z \in V} \bigl(f_{y,z} - f_{z,y}\bigr)\\ &= \sum_{y \in R} \sum_{z \in R} \bigl(f_{y,z} - f_{z,y}\bigr) + \sum_{y \in R} \sum_{z \notin R} \bigl(f_{y,z} - f_{z,y}\bigr)\tag{6.5}\\ &= \sum_{y \in R} \sum_{z \notin R} \bigl(f_{y,z} - f_{z,y}\bigr)\tag{6.6}\\ &\le \sum_{y \in R} \sum_{z \notin R} f_{y,z}.\tag{6.7} \end{align}

(6.6) follows because the first sum in (6.5) contains the flow along every edge \((y, z)\) with \(y, z \in R\) twice, once with positive sign and once with negative sign. Thus, this sum is zero. (6.7) follows because \(f_{z,y} \ge 0\) for every pair of vertices \(y, z \in V\).

Since \(\sum_{y \in R} \sum_{z \notin R} f_{y,z} > 0\), there exists an edge \((y, z)\) with \(y \in R\) and \(z \notin R\) such that \(f_{y,z} > 0\), a contradiction. ▨

The next lemma states the main claim of this section: that every pseudo-flow \(f\) can be decomposed into a collection of path and cycle flows. It also provides a bound on the number of path and cycle flows in the decomposition and states that there exists such a decomposition consisting of only cycle flows if \(f\) is a circulation.

Lemma 6.5: Any pseudo-flow \(f\) in a network \(G\) can be represented as a sum of \(t \le n + m\) path or cycle flows \(f^{(1)}, \ldots, f^{(t)}\) in \(G\). If \(f\) is a circulation, then \(t \le m\) and \(f^{(1)}, \ldots, f^{(t)}\) are all cycle flows.

Proof: Consider a vertex supply balance function \(b\) defined as

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

Then \(f\) is a flow with respect to this vertex supply balance function. Let \(\Phi(f)\) be the number of edges \(e \in G\) such that \(f_e > 0\) and let \(\Psi(f)\) be the number of supply and demand vertices with respect to \(b\). We have \(\Phi(f) \le m\) and \(\Psi(f) \le n\). The first part of the proof uses induction on \(\Psi(f) + \Phi(f)\) to show that any pseudo-flow \(f\) can be written as the sum of a circulation \(f'\) plus \(t_1 \le \Psi(f) + \Phi(f) - \Phi(f')\) path flows \(p^{(1)}, \ldots, p^{(t_1)}\). The second part of the proof uses induction on \(\Phi(f')\) to show that any circulation \(f'\) can be written as the sum of \(t_2 \le \Phi(f')\) cycle flows \(o^{(1)}, \ldots, o^{(t_2)}\). Together, these two claims show that \(f\) can be written as the sum of \(t_1 + t_2 \le \Psi(f) + \Phi(f) - \Phi(f') + \Phi(f') = \Psi(f) + \Phi(f) \le n + m\) cycle and path flows \(p^{(1)}, \ldots, p^{(t_1)}, o^{(1)}, \ldots, o^{(t_2)}\). Moreover, if \(f\) is a circulation, then \(\Psi(f) = 0\), so we obtain a decomposition of \(f\) into \(t_2 \le \Phi(f) \le m\) cycle flows \(o^{(1)}, \ldots, o^{(t_2)}\).

Decomposing \(\boldsymbol{f}\) into a circulation and path flows: If \(\Psi(f) = 0\), then \(f\) is a circulation and can thus be written as the sum of \(f\) itself and \(0 = \Psi(f) + \Phi(f) - \Phi(f)\) path flows. So assume that \(\Psi(f) > 0\). By Lemma 6.4, there exists a path \(P\) in \(G\) from a supply vertex \(x\) to a demand vertex \(y\) such that \(f_e > 0\) for every edge \(e \in P\). Let

\[\delta = \min (\{ b_x, -b_y \} \cup \{ f_e \mid e \in P \}),\]

let \(p^{(1)}\) be the path flow defined as

\[p^{(1)}_e = \begin{cases} \delta & \text{if } e \in P\\ 0 & \text{otherwise,} \end{cases}\]

and let \(f'' = f - p^{(1)}\).

\(p^{(1)}\) is easily seen to be a path flow: We have \(0 \le p^{(1)}_e \le f_e \le u_e\) for every edge \(e \in G\) because \(f\) is a pseudo-flow, every vertex \(z \notin \{x, y\}\) satisfies

\[\sum_{z \in V} \bigl(f_{z,w} - f_{w,z}\bigr) = 0,\]

and the edges with \(p^{(1)}_e > 0\) form the path \(P\).

\(f''\) is a pseudo-flow because \(0 \le p^{(1)}_e \le f_e\) for every edge \(e \in G\), so \(0 \le f''_e = f_e - p^{(1)}_e \le f_e \le u_e\) for every edge \(e \in G\).

The vertex supply balance function \(b''\) defined as

\[b''_z = \begin{cases} b_z - \delta & \text{if } z = x\\ b_z + \delta & \text{if } z = y\\ b_z & \text{if } z \notin \{x, y\} \end{cases}\]

turns \(f''\) into a flow. Moreover, we have \(\Phi(f'') \le \Phi(f)\) and \(\Psi(f'') \le \Psi(f)\), and at least one of these two inequalities is strict. Indeed, if \(\delta = b_x\) or \(\delta = -b_y\), then \(\Psi(f'') < \Psi(f)\); if \(\delta = f_e\) for some edge \(e \in P\), then \(\Phi(f'') < \Phi(f)\). Thus, \(\Phi(f'') + \Psi(f'') < \Phi(f) + \Psi(f)\) and, by the induction hypothesis, \(f''\) can be written as the sum of a circulation \(f'\) and \(t_1 - 1 \le \Psi(f'') + \Phi(f'') - \Phi(f') \le \Psi(f) + \Phi(f) - \Phi(f') - 1\) path flows \(p^{(2)}, \ldots, p^{(t_1)}\). Since \(f = p^1 + f''\) and \(p^{(1)}\) is a path flow, \(f\) can therefore be written as the sum of \(f'\) and \(t_1 \le \Psi(f) + \Phi(f) - \Phi(f')\) path flows \(p^{(1)}, \ldots, p^{(t_1)}\).

Decomposing a circulation into cycles: Let \(f'\) be a circulation. If \(\Phi(f') = 0\), then \(f'_e = 0\) for every edge \(e \in G\) and \(f'\) can be written as the sum of \(0 = \Phi(f')\) cycle flows. If \(\Phi(f') > 0\), then let \(G^+ = (V, E^+)\), where \(E^+ = \{ e \in E \mid f'_e > 0 \}\) is the set of edges used by \(f'\). Since \(f'\) is a circulation, \(G^+\) has no vertex with only in-edges or only out-edges. Thus, since \(\Phi(f') > 0\) and therefore \(E^+ \ne \emptyset\), there exists a cycle \(C\) in \(G^+\). Let \(\delta = \min_{e \in C} f'_e\). Then we define \(o^{(1)}\) as

\[o^{(1)}_e = \begin{cases} \delta & \text{if } e \in C\\ 0 & \text{otherwise} \end{cases}\]

and \(f''\) as \(f'' = f' - o^{(1)}\).

\(o^{(1)}\) is easily seen to be a cycle flow: All edges satisfy their capacity constraints, every vertex \(x \in V\) satisfies

\[\sum_{y \in V} \bigl(f_{x,y} - f_{y,x}\bigr) = 0,\]

and the edges with \(o^{(1)}_e > 0\) form the cycle \(C\).

Since both \(f'\) and \(o^{(1)}\) are circulations, we have

\[\sum_{y \in V} \bigl(f''_{x,y} - f''_{y,x}\bigr) = \sum_{y \in V} \bigl(f'_{x,y} - f'_{y,x}\bigr) - \sum_{y \in V} \Bigl(o^{(1)}_{x,y} - o^{(1)}_{y,x}\Bigr) = 0 \quad \forall x \in V.\]

By an argument similar to the first part of the proof, \(f''\) also satisfies the capacity constraints of \(G\). Thus, \(f''\) is a circulation in \(G\).

Since \(f'_e = \delta\) for at least one edge \(e \in C\), we have \(\Phi(f'') < \Phi(f')\). Thus, by the induction hypothesis, \(f''\) can be written as the sum of \(t_2 - 1 \le \Phi(f'') \le \Phi(f') - 1\) cycle flows \(o^{(2)}, \ldots, o^{(t_2)}\). Since \(o^{(1)}\) is a cycle flow and \(f' = f'' + o^{(1)}\), \(f'\) can thus be written as the sum of \(t_2 \le \Phi(f')\) cycle flows \(o^{(1)}, \ldots, o^{(t_2)}\). ▨