Skip to main content

Math 428/529: Discrete Optimization

Jonathan A. Noel

Section 3.6 Network Flows

The focus of this section is on network flow problems in graphs and digraphs. The setup is that you are given a digraph \(D\) with a capacity function \(c:A(D)\to\mathbb{R}\text{,}\) a source vertex \(s\) and a sink vertex \(t\text{.}\) We want to pump a commodity (e.g. water, oil, etc) through the network from the source \(s\) to the sink vertex \(t\) at the maximum rate possible. Naturally, at every vertex except for \(s\) and \(t\text{,}\) the total amount of incoming flow must be equal to the total amount of outgoing flow; i.e. “Kirchoff’s current law” is obeyed at all such vertices. Let us make this more precise. Given a vertex \(u\) in a digraph, let \(N^+(u)\) and \(N^(u)\) be the sets of all out-neighbours and in-neighbours, respectively.

Definition 3.6.1.

Let \(D\) be a digraph, let \(s,t\in V(D)\) and let \(c:A(D)\to [0,\infty)\) be a function, where \(c(uv)\) is the capacity of the arc \(uv\in A(D)\text{.}\) A flow in \(D\) from \(s\) to \(t\) with respect to \(c\) is a function \(f:A(D)\to [0,\infty)\) such that
  • \(\sum_{v\in N^+(u)}f(uv)=\sum_{v\in N^-(u)} f(vu)\) for all \(u\in V(D)\setminus\{s,t\}\) and
  • \(f(uv)\leq c(uv)\) for all \(uv\in A(D)\text{.}\)
The value of the flow \(f\) is defined to be \(\sum_{v\in N^+(s)}f(sv)-\sum_{v\in N^-(s)}f(vs)\text{.}\)

Problem 3.6.2. The Max-Flow Problem.

  • Input: A digraph \(D\text{,}\) vertices \(s,t\in D\) and a capacity function \(c\text{.}\)
  • Problem: Find a flow in \(D\) from \(s\) to \(t\) with respect to \(c\) of maximum value.
The concept of duality will play a key role here, once again. A guiding philosophy in this course is to come up with an “obvious” obstruction for the existence of a mathematical structure (e.g. a small vertex cover is an obvious obstruction for a large matching) and show that this is, in fact, the only obstruction (as is the case for vertex covers in bipartite matching problems). In this setting, the key bottleneck is a set of arcs of low total capacity whose deletion destroys all paths from \(s\) to \(t\text{.}\) To make this more precise, given a set \(U\) of vertices, define \(\partial^+(U)\) to be the set of all arcs that have their first vertex in \(U\) and second vertex outside of \(U\) (i.e. they point out of \(U\)). A set \(U\) of vertices is called an \((s,t)\)-cut if \(s\in U\) and \(t\notin U\text{.}\) The capacity of an \((s,t)\)-cut is the sum of capacities of all arcs in \(\partial^+(U)\text{.}\) As it turns out, the problem of finding the minimum capacity of an \((s,t)\)-cut is the dual of the problem of finding the maximum value of a flow.
The above theorem immediately implies that the problem of deciding whether there exists a flow of value at least, say, \(\alpha\in\mathbb{Q}\) is in \(\text{NP}\cap\text{co-NP}\text{,}\) which is good evidence that it is in P. Unsurprisingly, it is indeed possible to give explicit polynomial time algorithm to solve it. We will not describe those algorithms here, but we note that there is an exercise in Section 6.4 which shows how it can be reduced in polynomial-time to an LP, and so it is indeed polynomial-time solvable.
Let us now present a proof of the Max-Flow Min-Cut Theorem by building it up slowly from some related results. First, we start with the “vertex version” of Menger’s Theorem. Note that we will focus on the case of digraphs here, but all of these results also apply to graphs because a graph can be represented by a digraph by replacing each edge \(uv\) with two “symmetric” arcs; one from \(u\) to \(v\) and one from \(v\) to \(u\text{.}\)

Definition 3.6.4.

Given two sets \(S\) and \(T\) of vertices in a digraph \(D\text{,}\) an \((S,T)\)-vertex cut is a set \(C\subseteq V(D)\) such that every walk from \(S\) to \(T\) passes through \(C\text{.}\) Note that \(C\) may have elements in common with \(S\cup T\text{.}\)

Proof.

If \(C\) is an \((S,T)\)-vertex cut, then any path from \(S\) to \(T\) must contain a vertex of \(|C|\text{,}\) and so, by the Pigeonhole Principle, there cannot be more than \(|C|\) such paths which are pairwise disjoint. This proves that the maximum is at most the minimum.
Now, we prove the other direction by induction on \(|A(D)|\text{.}\) Let \(k\) be the minimum cardinality of an \((S,T)\)-vertex cut. Our goal is to show that there are \(k\) vertex disjoint paths from \(S\) to \(T\text{.}\) Let \(uv\) be any arc of \(D\text{.}\) If the minimum \((S,T)\)-vertex cut in \(D\setminus\{uv\}\) has cardinality \(k\text{,}\) then, by induction, we can find the desired paths in \(D\setminus\{uv\}\) and therefore in \(D\text{.}\) So, we can let \(C\) be an \((S,T)\)-vertex cut of cardinality at most \(k-1\) in \(D\setminus\{uv\}\text{.}\) Since \(C\cup \{u\}\) is an \((S,T)\)-vertex cut in \(D\text{,}\) we must have \(|C|\geq k-1\text{,}\) and so \(|C|=k-1\text{.}\) Define \(C_u:=C\cup \{u\}\) and \(C_v:= C\cup \{v\}\text{.}\) Our strategy now will be to find \(k\) disjoint paths from \(S\) to \(C_u\) and from \(C_v\) to \(T\) and “stitch them together” to get \(k\) disjoint edges from \(S\) to \(T\text{.}\)
We start by building \(k\) disjoint paths from \(S\) to \(C_u\) in \(D\setminus\{uv\}\text{.}\) If we cannot, then, by induction, there is a set \(X\) of cardinality at most \(k-1\) such that every walk from \(S\) to \(C_u\) in \(D\setminus\{uv\}\) passes through \(X\text{.}\) However, this set \(X\) is an \((S,T)\)-vertex cut in \(D\) since any walk from \(S\) to \(T\) in \(D\) passes through \(C_u\) and, therefore, can be shortened to a walk from \(S\) to \(C_u\) in \(D\setminus\{uv\}\text{.}\) So, we must have \(|X|\geq k\text{.}\) Thus, by induction, there are \(k\) vertex disjoint paths from \(S\) to \(C_u\) in \(D\setminus\{uv\}\text{.}\) Since \(|C_u|=k\text{,}\) for each \(c\in C_u\text{,}\) there is exactly one of these paths ending at \(c\text{;}\) call it \(P_c\text{.}\) Similarly, we can find \(k\) vertex disjoint paths from \(C_v\) to \(T\) in \(D\setminus\{u,v\}\) and, for \(c\in C_v\text{,}\) let \(Q_c\) be the path from this set starting at \(c\text{.}\)
Now, for each \(c\in C\text{,}\) let \(R_c\) be the walk obtained by concatenating \(P_c\) and \(Q_c\text{.}\) Also, let \(R_{uv}\) be the walk obtained by concatenating \(P_u\) with the arc \(uv\) and then the path \(Q_v\text{.}\) We claim that all of these walks are actually paths and that they are pairwise disjoint. The only way that this could go wrong is if there is some \(c\in C_u\) and \(c'\in C_v\) such that \(P_c\) intersects \(Q_{c'}\) at one of their internal vertices. However, if this happens, then we could start at a vertex of \(S\text{,}\) walk along \(P_c\) until it intersects with \(Q_{c'}\text{,}\) and then follow \(Q_{c'}\) until we reach \(T\text{.}\) This would give us a walk from \(S\) to \(T\) in \(D\setminus\{uv\}\) that does not pass through \(C\text{,}\) which is a contradiction. This completes the proof.
From the “vertex version” of Menger’s Theorem, we can easily derive the following “arc version.”

Proof.

The line digraph of \(D\) is the digraph \(L(D)\) with vertex set \(A(D)\) where there is an arc in \(L(D)\) from one arc \(uv\) of \(D\) to another arc \(xy\) of \(D\) if and only if \(v=x\text{.}\) Let \(S\) be the set of all arcs of \(D\) that start at \(s\) and let \(T\) be the set of all arcs that end at \(t\text{.}\) We apply Theorem 3.6.5 to the sets \(S\) and \(T\) in \(L(D)\text{.}\) Note that a path from \(S\) to \(T\) in \(L(D)\) corresponds to a walk from \(s\) to \(t\) in \(D\) and, for any for any such walk, we can always shorten it to a path that contains a subset of the edges of the original walk. Also, an \((S,T)\)-vertex cut in \(L(D)\) of minimum size corresponds to a set of the form \(\partial^+(U)\) where \(U\) is an \((s,t)\)-cut. This completes the proof.
As we shall see next, the Max-Flow Min-Cut Theorem follows from the arc version of Menger’s Theorem by using duplicating arcs and taking a limit.

Proof of the Max-Flow Min-Cut Theorem.

First, let us show that the value of any flow \(f\) is at most the capacity of any \((s,t)\)-cut \(U\text{.}\) To see this, we bound the value of \(f\) as follows:
\begin{equation*} \sum_{u:su\in A(D)}f(su)-\sum_{u:us\in A(D)}f(us) = \sum_{v\in U}\left(\sum_{u:vu\in A(D)}f(vu)-\sum_{u:uv\in A(D)}f(uv)\right) \end{equation*}
\begin{equation*} =\sum_{uv\in \partial^+(U)}f(uv) - \sum_{uv\in \partial^-(U)}f(uv)\leq\sum_{uv\in \partial^+(U)}f(uv)\leq \sum_{uv\in \partial^+(U)}c(uv) \end{equation*}
which is precisely the capacity of \(\partial^+(U)\text{,}\) and so this completes this part of the proof.
Now, we prove that the value of the max-flow , suppose that the capacities are integers. In this case, we can replace each arc \(uv\) of \(D\) by \(c(uv)\) parallel arcs and apply Theorem 3.6.6. If the capacities are rational numbers, then multiply the capacities of all arcs by the lowest common multiple of the denominators of these rational numbers, say \(q\text{,}\) solve the resulting problem for integer capacities, and then divide the answer by \(q\text{.}\) If the capacities are general real numbers, then we solve a sequence of problems with rational capacities that converge to the real capacities. As there are only finitely many subsets of \(A(D)\text{,}\) there must be an infinite sequence of these problems for which the min-cuts are all the same. Each flow that we obtain for the rational flow problems in this subsequence can be viewed as a vector in \(\prod_{uv\in A(D)}[0,c(uv)]\text{,}\) which is a compact set. So, there is a convergent subsequence. The limit of this subsequence is a flow with value equal to that of the min-cut.
From the first part of the proof of the Max-Flow Min-Cut Theorem, it is evident that if all capacities of an instance of the max-flow problem are integer, then there exists an integer-valued max-flow. We state this as a separate theorem since we will use it in the next section.
Before moving on to discussing algorithms for the max-flow problem, we mention some special ideas related to the specialization of Menger’s Theorem to undirected graphs. A graph \(G\) is said to be \(k\)-connected if there does not exist a set \(C\) of cardinality \(k-1\) such that \(G\setminus C\) is either disconnected or contains a single vertex, and the connectivity of \(G\) is the maximum \(k\) such that \(G\) is \(k\)-connected. Similarly, a graph is \(k\)-edge connected if there does not exist a set of \(k-1\) edges whose removal disconnects the graph, and its edge connectivity is the maximum \(k\) for which it is \(k\)-edge connected. The following are consequences of the two Menger’s Theorems proved above.

Subsection 3.6.1 Algorithms for Maximum Flows

Let us now talk about how to find a maximum flow algorithmically. It is not hard to see that this can be reduced to solving a linear program (Exercise 42) and so it is polynomial-time solvable. However, as with the maximum weight matching problem, there also exist more intuitive combinatorial algorithms. Here, we describe one known as the Ford-Fulkerson Algorithm. The idea of the algorithm is to start with a null flow \(f\) which maps every arc to \(0\) and then repeatedly “augment” it to obtain a flow of higher value until we find a cut of low capacity which prevents this. The key subroutine is the following “flow augmentation algorithm”.
As we said above, given the flow augmentation algorithm, it is straightforward to come up with an algorithm for finding a maximum flow. That is, start with the flow that assigns every arc to 0 and then augment it repeatedly until the augmentation algorithm outputs a min cut and then you’re done. However, what is not clear is whether this is an efficient algorithm. As it turns out, it is actually very far from being efficient. If some of your capacities are irrational and you do not choose your augmenting paths carefully, then it could actually run forever; see this paper for an example.
If all of the capacities are rational, then we can avoid the issue of infinite running time because, if \(N\) is the least common multiple of all of the denominators of the capacities, then, in every augmentation, \(\varepsilon\) will be an integer multiple of \(1/N\) and so the algorithm must terminate. However, while it will terminate eventually, it may take a very long time, even for small digraphs, as the next example shows.

Example 3.6.11.

Consider the following instance of the max-flow problem. The vertices \(s\) and \(t\) are labelled and each arc is labelled with its capacity. If you’d like, you can imagine replacing the \(\infty\) arcs with arcs of very high capacity.
In the Ford-Fulkerson algorithm, it is possible that the algorithm will always augment along an \((s,t)\)-path with three arcs in \(D_f\text{.}\) If so, then every augmentation increases the value of the flow by exactly 1. So, the algorithm will be running for a very long time!
The above example shows that the Ford-Fulkerson algorithm has the unfortunate property that the running time is highly sensitive to the choice of the augmenting path and specific capacity function (i.e. the running time could be large even if the graph is tiny). However, one may observe that a maximum flow could be found much faster in the above example if we would have chosen our augmenting paths differently. As we will show next, we can always obtain a running time that is bounded only in terms of the digraph \(D\) (and not in terms of the capacity function) by choosing the augmenting paths more carefully.

Proof.

Again, we start with the zero flow and repeatedly apply the flow augmentation algorithm. The only difference is that, this time, we will be careful to ensure that that in every application of the flow augmenting algorithm, we always augment along an \((s,t)\)-path in \(D_f\) with the minimum number of arcs. In each iteration, the number of steps that it takes to find the path with the minimum number of arcs and augment along it is \(O(|A(D)|)\text{.}\) Thus, it suffices to prove that the number of iterations is \(O(|V(D)||A(D)|)\text{.}\)
For any flow \((s,t)\)-flow \(f\text{,}\) let \(\dist(f)\) be minimum number of arcs in a path from \(s\) to \(t\) in \(D_f\) and let \(E_f\) be the set of arcs that are contained in at least one path from \(s\) to \(t\) with \(\dist(f)\) arcs in \(D_f\text{.}\)
Now, suppose that \(f'\) is a flow that is obtained from \(f\) by augmenting along a path \(P\) of with \(\dist(f)\) arcs from \(s\) to \(t\text{.}\) Let \(D^*\) be the digraph obtained from \(D_f\) by adding in the reversal of very arc in \(P\text{.}\) Note that \(D_f\) and \(D_{f'}\) are both subdigraphs of \(D^*\text{.}\) We claim that the minimum number of arcs in a path from \(s\) to \(t\) in \(D^*\) is \(\dist(f)\) and that \(E^*=E_f\) where \(E^*\) is the set of arcs contained in some path with \(\dist(f)\) arcs from \(s\) to \(t\text{.}\) If not, then there is some arc \(uv\in A(D_f)\) such that the reversal \(vu\) is not in \(D_f\) and there is a path \(Q\) with at most \(\dist(f)\) arcs from \(s\) to \(t\) in \(D^*\) going through \(vu\text{.}\) We can assume that \(vu\) is the last arc of \(Q\) that is not in \(D_f\text{.}\) But now take \(Q\) together with a path of length \(\dist(f)\) in \(D_f\) going through \(uv\) and we can use these arcs to get a path of length less than \(\dist(f)\) in \(D_f\text{,}\) a contradiction.
By the result of the previous paragraph, we have that \(\dist(f')\geq \dist(f)\) and, if \(\dist(f')=\dist(f)\text{,}\) then \(E_{f'}\subsetneq E_f\text{.}\) So, in every iteration, the pair \((\dist(f),|A(D)|-|E_f|)\) increases lexicographically. Since the first entry can only take on \(|V(D)|\) values and the second can only take on \(|A(D)|\) values, there are at most \(|V(D)||A(D)|\) iterations.
Here are two YouTube videos related to this section:
PrevTopNext