5.1.3.2. Finding a Blocking Flow

Lemma 5.9: A blocking flow in \(L^f\) can be found in \(O(nm)\) time.

Proof: To find a blocking flow \(b\) in \(L^f\), Dinitz's algorithm essentially applies the Ford-Fulkerson algorithm to \(L^f\), but with two twists:

First, instead of looking for arbitrary augmenting paths in the residual network \(L^{f,b}\), we only look for monotone augmenting paths. By definition, once we cannot find such a path, \(b\) is a blocking flow even if there exist other (non-monotone) augmenting paths in \(L^{f,b}\).

This allows us to get away with maintaining only part of \(L^{f,b}\): Since we never use backward edges in \(L^{f,b}\)—edges \((x,y)\) that satisfy \(\mathrm{dist}_{G^f}(s, x) = \mathrm{dist}_{G^f}(s, y) + 1\)—we do not need to construct them. The forward edges in \(L^{f,b}\) are edges of \(L^f\). Thus, we initialize \(L^{f,b} = L^f\) because the initial flow is \(b = 0\). As we saturate edges in \(L^{f,b}\)—we send \(u^{f,b}_e\) flow along an edge \(e \in L^{f,b}\)—we simply remove them.

Maintaining \(L^{f,b}\) as the subgraph of forward edges in the residual network of \(b\) has the advantage that a path in the residual network of \(b\) is monotone if and only if it is a path in \(L^{f,b}\). Thus, we can look for any \(st\)-path in \(L^{f,b}\). Once we do not find such a path, \(b\) is a blocking flow.

How often do we need to augment \(b\) before it becomes a blocking flow? Note that \(L^f\) has at most \(m\) edges: For every edge \((x,y)\) of \(G\), \(G^f\) may contain both edges \((x,y)\) and \((y,x)\), but at most one of them can be a forward edge. Since we initialize \(L^{f,b} = L^f\), \(L^{f,b}\) starts out with at most \(m\) edges. Each augmentation of \(b\) along some path \(P\) in \(L^{f,b}\) saturates at least one edge in \(P\). This edge is removed from \(L^{f,b}\). Thus, \(L^{f,b}\) has no edges left after at most \(m\) augmentations. At this point, \(b\) is obviously a blocking flow. Thus, it takes at most \(m\) augmentations of \(b\) to obtain a blocking flow in \(L^f\).

If we could find each monotone \(st\)-path in \(L^{f,b}\) used to augment \(b\) in \(O(n)\) time, finding a blocking flow would take \(O(nm)\) time as claimed because we just observed that we need to find at most \(m\) such paths. Finding these paths is the only hard part; given a monotone \(st\)-path \(P\) in \(L^{f,b}\), we can easily augment \(b\) in \(O(n)\) time: Since \(P\) is monotone, it has \(\ell^f \le n - 1\) edges. Inspecting all of these edges to find the one with minimum residual capacity \(u^{f,b}_e = \delta\) takes \(O(n)\) time. We can then inspect each edge in \(P\) a second time to increase the flow along it and decrease its residual capacity by \(\delta\). Any edge whose residual capacity becomes \(0\) is removed.

Unfortunately, finding a single monotone \(st\)-path in \(L^{f,b}\) may take much longer than \(O(n)\) time. Here is the second twist in the algorithm, which ensures that the algorithm nevertheless takes \(O(nm)\) time overall: We use depth-first search to find \(st\)-paths in \(L^{f,b}\), and we terminate each search as soon as we find a path from \(s\) to \(t\).

Let \(P_1, \ldots, P_r\) be the \(st\)-paths in \(L^{f,b}\) used to construct \(b\). We can divide the edges inspected to find each path \(P_i\) into two subsets: those in \(P_i\) and those not in \(P_i\). \(P_i\) has \(\ell^f \le n - 1\) edges. Let \(m_i\) be the number of inspected edges not in \(P_i\). Then finding \(P_i\) takes \(O(n + m_i)\) time. The cost of finding all paths \(P_1, \ldots, P_r\) is thus \(O\bigl(nm + \sum_{i=1}^r m_i\bigr)\) because \(r \le m\). Next we prove that we can ensure that \(\sum_{i=1}^r m_i \le m\). Thus, the overall running time of the algorithm for finding a blocking flow is \(O(nm)\), as claimed.

Consider the construction of \(P_i\). The key observation is that the \(m_i\) edges not in \(P_i\) that are inspected during the construction of \(P_i\) can be removed from \(L^{f,b}\) because they cannot belong to any \(st\)-path in \(L^{f,b}\). By removing these edges, we ensure that every edge of \(L^f\) is inspected during the construction of at most one path \(P_i\) without being part of this path. Thus, \(\sum_{i=1}^r m_i \le m\) follows immediately.

So let \(e\) be an edge not in \(P_i\) that is inspected during the construction of \(P_i\). Since we terminate the search for \(P_i\) as soon as we find the last edge of \(P_i\), that is, as soon as we reach \(t\), \(e\) is inspected before the last edge in \(P_i\). Since \(e \notin P_i\), this means that the depth-first search followed \(e\) and then backtracked across \(e\) before finding \(P_i\). In particular, the depth-first search explored all edges reachable from \(e\) without reaching \(t\). Thus, \(e\) is not part of any \(st\)-path in \(L^{f,b}\) at the time we construct \(P_i\). Since we never add any edge to \(L^{f,b}\), \(e\) cannot be part of any \(st\)-path in any subsequent iteration either, so \(e\) can safely be removed from \(L^{f,b}\). ▨

We have shown that a blocking flow can be found in \(O(nm)\) time, that augmenting a feasible \(st\)-flow with a blocking flow produces another feasible \(st\)-flow, and that at most \(n\) such augmentations are necessary to obtain a maximum \(st\)-flow. Thus, we have shown the following theorem:

Theorem 5.10: Dinitz's algorithm computes a maximum \(st\)-flow in \(O\bigl(n^2m\bigr)\) time.