Unit 5
An \(s\)-\(t\) network is given as a pair \(G, u\) where \(G = (\mathcal{N},\mathcal{A})\) is a digraph with distinct nodes \(s,t \in \mathcal{N}\) and \(0 \leq u_e \leq \infty\) is the capacity on the arc \(e \in \mathcal{A}\). We call the nodes \(s\) and \(t\) the source and sink, respectively. (Note that \(u_e \leq \infty\) means that \(u_e\) can be \(\infty\), meaning that no upper bound exists. In practice, \(\infty\) is sometimes replaced with a very large constant.) Unlike our discussion on the Minimum-Cost Flow Problem, we do not make simplifying assumptions on how the elements in \(\mathcal{N}\) and \(\mathcal{A}\) are labelled but we assume that each arc is uniquely identified by its head and its tail; that is, given nodes \(u,w \in \mathcal{N}\), there is at most one arc with \(u\) as tail and \(w\) as head so that if such an arc exists, it will be identified by \(uw\).
The Maximum \(s\)-\(t\) Flow Problem on \(G, u\) is defined as the following linear programming problem: \[\begin{array}{rll} \max & \mathbf{x}(\delta^{+}(s)) - \mathbf{x}(\delta^{-}(s)) \\ (MF)~~~~\text{s.t.}& \mathbf{x}(\delta^{+}(v)) - \mathbf{x}(\delta^{-}(v)) = 0 & \forall~v \in \mathcal{N}\setminus \{s,t\} \\ & 0 \leq x_e \leq u_e & \forall~e \in \mathcal{A}. \end{array}\] Here, the notation \(\mathbf{x}(S)\) represents \(\displaystyle\sum_{e \in S} x_e\). Thus, \(\mathbf{x}(\delta^{+}(s))\) represents \(\displaystyle\sum_{e \in \delta^{+}(s)} x_e\).
The equality constraints are called flow conservation constraints.
Any feasible solution to \((MF)\) is called an \(s\)-\(t\) flow and its objective function value is called its value. In other words, the Maximum \(s\)-\(t\) Flow Problem is to find an \(s\)-\(t\) flow having maximum value.
For example, consider the \(s\)-\(t\) network depicted in Figure 5.1. There is a pair of number next to each arc. The first number denotes the capacity on the arc.
Then \(\mathbf{x} \in \mathbb{R}^\mathcal{A}\) given by \(x_{sa} = x_{ac} = x_{cb} = x_{bt} = 1\) and \(x_{sc} = x_{ab} = x_{ct} = 0\) is an \(s\)-\(t\) flow of value 1. These values are the second numbers on the arcs.
The Maximum \(s\)-\(t\) Flow Problem has quite a few important applications. We will see some of these next week. In the meantime, we note that there is no difficulty in solving this problem as it is just a linear programming problem. However, the special form lends itself to combinatorial methods that have good bounds on the worst-case running times. We will look at one such algorithm.
The key ingredient to the augmenting path algorithm of Ford and Fulkerson (1956) is the notion of an augmenting path. Let \(\mathbf{x}\) be an \(s\)-\(t\) flow. Suppose that \(P\) is a path (not necessarily directed) from \(s\) to \(t\) such that for every forward arc \(e\), we have \(x_e < u_e\), and for every backward arc \(e\), we have \(x_e > 0\). Then for a sufficiently small \(\epsilon > 0\), we can obtain another \(s\)-\(t\) flow \(\mathbf{x}'\) given by \[x_e = \left\{\begin{array}{rl} x_e + \epsilon & \text{ if } e \in \mathcal{F}(P) \\ x_e - \epsilon & \text{ if } e \in \mathcal{B}(P) \\ x_e & \text{ otherwise.} \end{array} \right.\] where \(\mathcal{F}(P)\) denotes the set of forward arcs in \(P\) and \(\mathcal{B}(P)\) denotes the set of backward arcs in \(P\).
Note that the value of \(\mathbf{x}'\) is \(\epsilon\) more than that of \(\mathbf{x}\). We call \(P\) an augmenting path. In addition, we say that \(\mathbf{x}'\) is obtained from \(\mathbf{x}\) by augmenting along \(P\) by \(\epsilon\).
The maximum possible value for \(\epsilon\) is given by the minimum of \(\min\{ u_e - x_e : e \in \mathcal{F}(P)\}\) and \(\min\{ x_e : e \in \mathcal{B}(P)\}.\)
The following are examples of augmenting paths in the network depicted in Figure 5.1:
\(s, sc, c, ct, t\)
\(s, sa, a, ac, c, cb, b, bt, t\) (Every arc is a forward arc.)
\(s, sc, c, ac, a, ab, b, cb, c, ct, t\). (Note that \(ac\) and \(cb\) are backward arcs.)
Augmenting the flow \(\mathbf{x}\) along the third path by \(1\) gives the flow depicted in Figure 5.2 having value 2.
A maximum \(s\)-\(t\) flow can be obtained through repeated flow augmentations on augmenting paths provided that the capacities are rational. Otherwise, the process could fail to terminate. It is possible to remove the assumption on the capacities through Theorem 5.6 below.
The core task of the Ford-Fulkerson algorithm is therefore finding augmenting paths. To this end, we define the auxiliary digraph \(G(\mathbf{x})\) associated with an \(s\)-\(t\) flow \(\mathbf{x}\) as follows:
The node set is \(\mathcal{N}\).
For all \(v, w \in \mathcal{N}\), \(vw\) is an arc of \(G(\mathbf{x})\) if \(x_{vw} < u_{vw}\).
For all \(v, w \in \mathcal{N}\), \(wv\) is an arc of \(G(\mathbf{x})\) if \(x_{vw} > 0\).
For example, Figure 5.3 shows the auxiliary digraph associated with the flow depicted in Figure 5.2.
To find an augmenting path, we simply look for an \(s\)-\(t\) dipath in the auxiliary digraph. In the example above, there are two:
\(s, sa, a, ac, c, cb, b, bt, t\)
\(s, sa, a, ac, c, ct, t\)
The first corresponds to the augmenting path \[s, sa, a, ac, c, cb, b, bt, t\] and the second corresponds to the augmenting path \[s, sa, a, ac, c, ct, t.\] Augmenting the flow along the second path by \(2\) gives the flow depicted in Figure 5.4 having value 4.
Figure 5.5 shows that the auxiliary digraph associated with the new flow.
We see that there is no \(s\)-\(t\) dipath. The next result tells us that we have found a maximum \(s\)-\(t\) flow.
Theorem 5.1. An \(s\)-\(t\) flow \(\mathbf{x}\) is of maximum value if and only if there does not exist an augmenting path.
To prove this theorem, we need the notion of an \(s\)-\(t\) cut. We call \(C \subseteq \mathcal{A}\) an \(s\)-\(t\) cut if there exists \(R \subseteq \mathcal{N}\) such that \(s \in R\), \(t\notin R\), and \(C = \delta^{+}(R)\). The capacity of \(C\) is the quantity \(\mathbf{u}(C)\).
Proposition 5.2. Let \(R \subseteq \mathcal{N}\) with \(s \in R\) and \(t \notin R\). The value of an \(s\)-\(t\) flow \(\mathbf{x}\) is given by \[\mathbf{x}(\delta^{+}(R)) - \mathbf{x}(\delta^{-}(R)).\]
Proof (sketch). We add up the following equalities: \[\begin{align*} \mathbf{x}(\delta^{+}(s)) - \mathbf{x}(\delta^{-}(s)) & = \mathbf{x}(\delta^{+}(s)) - \mathbf{x}(\delta^{-}(s)) \\ \mathbf{x}(\delta^{+}(v)) - \mathbf{x}(\delta^{-}(v)) & = 0 & \forall~v \in R\setminus \{s\} \end{align*}\] (The first is simply an identity stating that the value of the flow is equal to the value of the flow. The rest are flow conservation constraints.) The left-hand side simplifies to \(\mathbf{x}(\delta^{+}(R)) - \mathbf{x}(\delta^{-}(R))\) as desired.
Corollary 5.3. The value of an \(s\)-\(t\) flow is at most \(\mathbf{u}(C)\) for any \(s\)-\(t\) cut \(C\).
Proof of Theorem 5.1. It is clear that if there exists an augmenting path, \(\mathbf{x}\) flow cannot be of maximum value.
We now prove the converse. By Corollary 5.3, it suffices to construct an \(s\)-\(t\) cut \(C\) so that the value of \(\mathbf{x}\) is equal to \(\mathbf{u}(C)\). To this end, let \(R\) denote the set of nodes \(w\in \mathcal{N}\) such that there is a directed \(s\)-\(w\) path in \(G(\mathbf{x})\), the auxiliary digraph associated with \(\mathbf{x}\). We show that \[\mathbf{u}(\delta^{+}(R)) = \mathbf{x}(\delta^{+}(R)) - \mathbf{x}(\delta^{-}(R))\] and the result then follows from Proposition 5.2. To this end, consider \(uw \in \delta^{+}(R)\). Note that \(vw \notin G(\mathbf{x})\) or \(w\) would be included in \(R\). Hence, we must have \(x_{vw} = u_{vw}\). Now, consider \(vw \in \delta^{-}(R)\). Note that \(wv \notin G(\mathbf{x})\) or \(w\) would be included in \(R\). Hence, we must have \(x_{vw} = 0\). Hence, \[\mathbf{x}(\delta^{+}(R)) - \mathbf{x}(\delta^{-}(R)) = \mathbf{u}(\delta^{+}(R)) - 0 = \mathbf{u}(\delta^{+}(R))\] as desired.
Note that the proof shows a way to construct an \(s\)-\(t\) cut whose capacity is equal to the maximum flow value. For example, for the auxiliary digraph depicted in Figure 5.5, the set \(R\) will be \(\{s,a\}\). Hence, \(C = \delta^{+}(R) = \{ab, ac, sc\}\), giving \(\mathbf{u}(C) = u_{ab}+u_{ac}+u_{sc} = 1+2+1 = 4\), which is the value of the \(s\)-\(t\) flow depicted in Figure 5.4.
We can see from Corollary 5.3 that no \(s\)-\(t\) cut can have capacity less than the value of a maximum \(s\)-\(t\) flow. But we saw that we can indeed obtain an \(s\)-\(t\) cut that has capacity matching the value of a maximum \(s\)-\(t\) flow. These observations can be summarized as the next well-known result.
Theorem 5.4. (Max-Flow-Min-Cut Theorem) If there exists a maximum \(s\)-\(t\) flow, then the maximum value of an \(s\)-\(t\) flow equals the minimum capacity of an \(s\)-\(t\) cut.
A consequence of the augmenting path algorithm is the following:
Proposition 5.5. If all the finite arc capacities are integral, then there is a maximum \(s\)-\(t\) flow that is integral.
This result is useful in certain applications dealing with indivisible quantities.
The following result is due to Dinits (1970) and Edmonds and Karp (1972):
Theorem 5.6. If the shortest path in the auxiliary digraph is chosen in each augmentation, then there are at most \(nm\) augmentations where \(n = |\mathcal{N}|\) and \(m = |\mathcal{A}|\).
It can be shown that for the network depicted in Figure 5.6, if the augmenting paths are chosen arbitrarily, the number of augmentations could become \(2\cdot 10^k\).
Consider the \(s\)-\(t\) network depicted in Figure 5.6. Let \(\mathbf{x}\) denote the \(s\)-\(t\) flow with \(x_{ab} = 0\) and \(x_{sa} = x_{sb} = x_{at} = x_{bt} = f\) where \(f\) is an integer satisfying \(0\leq f < 10^k\).
Show that the \(s\)-\(t\) path given by \(s,sa, ab, b, bt,t\) is an augmenting path. What is the maximum flow amount that \(\mathbf{x}\) can be augmented by along this augmenting path?
Let \(\mathbf{x}'\) denote the \(s\)-\(t\) flow obtained from augmenting the flow along the augmenting path in part (a). Show that the \(s\)-\(t\) path given by \(s,sb,ab,a,at,t\) is an augmenting path. What is the maximum flow amount that \(\mathbf{x}'\) can be augmented by along this augmenting path?
Let \(G = (\mathcal{N}, \mathcal{A})\) denote the digraph depicted below:
Let \(\mathbf{u} = \begin{bmatrix} 4 & \infty & 2 & 3 & 3 & 1 & \infty & 2 & 5 \end{bmatrix}^\mathsf{T}\) so that \(u_i\) denotes the capacity on the arc \(e_i\) for \(i = 1,\ldots, 9\).
For each of the followng \(S\), give the value of \(\mathbf{u}(\delta^{+}(S))\).
\(S = \{s, a\}\).
\(S = \{s, a, b\}\).
\(S = \{s, b, c\}\).
Consider the \(s\)-\(t\) flow \(\mathbf{x} = \begin{bmatrix} 4 & 1 & 2 & 2 & 3 & 0 & 0 & 2 & 5 \end{bmatrix}^\mathsf{T}\) so that \(x_i\) denotes the flow value on the arc \(e_i\).
Form the auxiliary digraph \(G(\mathbf{x})\).
Find two \(s\)-\(t\) dipaths in \(G(\mathbf{x})\).
Augment the flow along the augmenting path corresponding to one of the dipaths in part b.
Obtain a maximum \(s\)-\(t\) flow and a minimum-capacity \(s\)-\(t\) cut.
Show that if there exists a maximum \(s\)-\(t\) flow to an \(s\)-\(t\) network, then there exists a maximum \(s\)-\(t\) flow \(\mathbf{x}^*\) such that \(\mathbf{x}^*(\delta^{-}(s)) = \mathbf{x}^*(\delta^{+}(t)) = 0\). (Hint: Look at the \(s\)-\(t\) flow at termination of the augmenting path algorithm.)
Note that the arcs \(sa,ab,bt\) are forward arcs in the given \(s\)-\(t\) path, call it \(P\), wth flow values on these arcs less than the corresponding arc capacities. Hence, \(P\) is an augmenting path. From the arc \(ab\), we see that the increase in flow value cannot exceed \(1-0 = 1\) since \(f\) is an integer less than \(10^k\), we have \(f+1\leq 10^k\), implying that the maximum flow increasing by augmenting along \(P\) path is 1.
Augmenting along \(P\) in part (a) results in the \(s\)-\(t\) flow \(\mathbf{x}'\) with \(x'_{ab} = 1\), \(x_{sa} = x_{bt} = f+1\) and x_{sb} = x_{at} =f$. Note that the arcs \(sb,at\) are forward arcs in the given \(s\)-\(t\) path, call it \(P'\), with flow values on these arcs less than the corresponding arc capacities, and the arc \(ab\) is a backward arc in \(P'\) with positive capacity. Hence, \(P'\) is an augmenting path. From the arc \(ab\), we see that the increase in flow value cannot exceed \(1\) since augmenting along \(P'\) decreases the flow value on \(ab\) by at most the flow value on the arc. But we can indeed increase the flow value by 1 augmenting along \(P'\) since the other arcs are forward arces with flow value at least 1 less than the corresponding capacities.
Remark. Combining the results in both parts, we obtain that starting the augmenting path algorithm with the \(s\)-\(t\) flow that is zero everywhere could result in \(2\cdot 10^k\) augmentations to reach a maximum flow if Theorem 5.6 is not used.
\(\mathbf{u}(\delta^{+}(\{s,a\})) = u_3+u_4+u_5+u_6 = 2+3+3+1=9\).
\(\mathbf{u}(\delta^{+}(\{s,a,b\}))=u_4+u_5+u_6+u_7+u_8=3+3+1+\infty+2=\infty\).
\(\mathbf{u}(\delta^{+}(\{s,b,c\})) = u_1+u_8+u_9 = 4+2+5=11\).
The auxiliary digraph is depicted below:
There is the dipath with node-sequence \(s,c,a,t\) and the dipath with node-sequence \(s,a,t\).
We can augment the flow by 1 unit on the path \(s, e_2, a, e_6, t\) to obtain the \(s\)-\(t\) flow \(\begin{bmatrix} 4 & 0 & 2 & 2 & 3 & 1 & 0 & 2 & 5 \end{bmatrix}^\mathsf{T}\) with flow value \(8\).
Note that the \(s\)-\(t\) cut given by \(\delta^{+}(\{s,a,c\})\) has capacity 8 which matches the flow value of the \(s\)-\(t\) flow in the previous part. Hence, \(\delta^{+}(\{s,a,c\})\) is a minimum-capacity \(s\)-\(t\) cut and the \(s\)-\(t\) flow in the previous part is a maximum \(s\)-\(t\) flow.
Alternatively, one can obtain the auxiliary digraph and note that there is no \(s\)-\(t\) dipath.
From the description of the augmenting path algorithm, it is clear that if one starts with the zero flow, no arc in \(\delta^{-}(s)\) or in \(\delta^{+}(t)\) can get a positive flow value. Hence, this property persists until termination.