Section 2: Max-Flow Min-Cut and Its LP Relatives
2.1 Introduction
n this section, we discuss a series of closely related combinatorial results - all with a unifying linear programming (LP) flavor.
2.2 Network Flows
Let D be a digraph with two distinguished vertices, a source s and a sink t. All edges incident with s are oriented away from s and all edges incident with t are oriented towards t. For every edge (i, j), there is a non-negative capacity c(i, j). A flow in such a network is an assignment of a nonnegative value x(i, j) to each edge (i, j) so that:
Given a flow, an edge (i, j) is full if x(i, j) = c(i, j) and it is empty if x(i,j) = 0.
The value of the flow is the quantity Σ_i x(s, i). Note that this quantity is the same as Σ_i x(i, t) and represents the total amount of flow through the network. Now the problem is to find a flow of maximum value.
In the following diagram, we will illustrate a flow of value 29 in a network. On each edge, the first number is the capacity while the second is the flow. One edge is empty but there are no full edges.
A partition of the vertex set V as the union of two disjoint sets S and T with s in S and t in T is called a cut. The capacity of a cut (S, T) is the sum of the capacity of all edges from S to T. It is an easy exercise to show that the value of any flow cannot exceed the capacity of any cut. And the Max-Flow Min-Cut theorem asserts that the maximum value of a flow in fact equals the minimum capacity of a cut.
Theorem [Max-Flow Min-Cut] The maximum value of a flow equals the minimum capacity of a cut.
Proof. W begin by describing a Labeling Algorithm which provides an efficient approach to finding a maximum flow and a minimum cut.
Start with any flow. For example, just start by assigning
flow zero to all edges. Given a flow, form an auxiliary
digraph D on the same vertex set as the network. But in D, we have
an edge (i, j) oriented from i to j
if either (1) x(i, j) < c(i, j) or (2) x(j ,i) > 0.
It is important to note that the digraph D depends on the flow.
Assign each edge in D weight 1.
For the moment, we assume that there is at least one
directed path in D from source s to sink
t.
Any such path is called an augmenting path. As we
travel along such an augmenting path from s to t, we traverse edges of the network in either
forward or backward direction. For each forward edge (i, j), let δ(i, j) = c(i, j)
- x(i, j). and for each backwards edge (i, j), let δ(i, j) = x(i, j). Then let
δ be the minimum value of δ(i, j) taken over all the
edges in the augmenting path. Note that δ > 0. We then augment the flow by
increasing the flow on each forward edge by δ while decreasing the
flow by δ on each backwards edge. These changes preserve the
requirements of a flow but now the value of the flow has been increased by δ.
In the following diagram, we show an augmenting path with δ = 3. The
red edges are forward edges and the blue edge is backwards.
Now suppose that there no augmenting paths. In this case, let R be the set of vertices reachable from source s in the auxiliary digraph D, and let U be the unreachable vertices, i.e., the remaining vertices. Of course, s is in R and t is in U. Then consider the edges with one endpoint in R and the other in U. The forward edges are full, and the backwards edges are empty. Furthermore the sum of the flow on the forward edges is the value of the flow. So we have in hand both a maximum flow and a minimum cut with the value of the flow equal to the capacity of the cut - exactly what we wanted.
It is easy to see that the number of augmentations is bounded and that eventually, the algorithm must halt. QED
We illustrate the Max-Flow Min-Cut theorem in the following diagram where the reachable vertices are colored beige and the unreachable ones are colored red. The green edges are full and the blue edge is empty.
When the current flow is not maximum, we can increase the value of the flow using any augmenting path. However, the number of augmentations can be affected by the numerical values of the capacities. Here is the standard example of this phenomenon. Although the maximum value of a flow in this network is 2M, it can take 2M augmentations to reach this value if we always take an augmenting path containing the edge with capacity 1.
Lemma. If we always choose an augmenting path of minimum length, then the algorithm will halt after at most O(n^3) augmentations.
Proof. The lemma follows from the following three elementary facts concerning distances in the auxiliary digraph D. With each augmentation:
QED
Clearly, a Max-flow problem is a special case of a linear programming problem, but it is not typically solved with standard LP machinery. The Labeling Algorithm is an instance of a Primal/Dual approach to LP problems.
Integer Solutions to Linear Programming Problems. In
general, when a LP problem is posed with integer coefficients, the solution will
involve rationals which are not integers. But a max-flow problem with
integer capacities always admits a solution in integers -as is evidenced by the
Labeling Algorithm. In
particular, if the capacities are all 0 or 1,
then there is a maximum flow in which each edge has flow 0 or 1.
This gives a distinctly combinatorial interpretation of the underlying network
flow problem.
2.3 Bipartite Matching
Let G = (A, B, E) be a bipartite graph, and let A' be a subset of A. An injection f from A' to B is called a matching of A' into B when a is adjacent to f(a) in G, for every vertex a in A'. In the following diagram, the red edges form a matching of A into B.
Let G = (A, B, E) be a bipartite graph. For each subset S of A, let N(S) denote the subset of B consisting of those vertices which are adjacent to one or more vertices in A. Clearly, if there exists a matching of A into B, then the following condition holds:
Hall's Matching Condition: |N(S)| ≥ |S| for every subset S of A.
in the following diagram, there are three red vertices in A. Their two neighbors in B are colored blue. In this bipartite graph, there is no matching of A into B.
Hall's theorem then asserts that this obvious necessary condition is also sufficient.
Theorem [P. Hall] There is a matching of A into B if and only if |N(S)| ≥ |S| for every subset S of A.
Proof. We need only prove sufficiency. We argue by contradiction and consider a counterexample on the minimum number of vertices. Suppose first that |N(S)| > |S| for every subset S of A with S a non-empty proper subset of A. In this case, choose an arbitrary vertex a from A and then let b be any neighbor of a from B. Remove a and b from the graph and note that the condition holds for the resulting subgraph. Hence there is a matching of A - {a} into B - {b}, which together with the edge ab forms a matching of A into B.
It follows that there is a nonempty proper subset S of A with |N(S)| = |S|. In this case, we consider two bipartite graphs G_1 = (S, N(S)) and G_2 = (A - S, B - N(S)). It is easy to see that Hall's matching condition holds for G_1 so there is matching of S into N(S). But we claim Hall's matching condition also holds in G_2. To see this, note that if T is a subset of A - S, then N(T υ S) = N(S) υ W, where W is the set of neighbors of T in G_2. It follows that there is a matching of A - S into B - N(S). Together these two matchings form a matching of A into B. QED
More generally, given a bipartite graph G = (A, B, E), one could ask for the least non-negative integer d = d(G) for which there is a subset A' of A for which there is a matching of A' into B with |A'| = |A| - d. This is just the problem of finding a maximum matching in the bipartite graph G. The following corollary is called the defect form of Hall's theorem.
Corollary. Let G = (A, B, E) be a bipartite graph and let d be a nonnegative integer. Then there exists a subset A' of A with |A'| = |A| - d for which there is a matching of A' into B if and only if |N(S)| ≥ |S| - d for every subset S of A.
Proof. Without loss of generality d > 0. Suppose first that there is a subset A' of A with |A'| = |A| - d for which there is a matching of A' into B. Then let S be any subset of A. It follows immediately that |N(S)| ≥ |S| - d, since S contains at most d elements which do not belong to A'.
Now suppose that N(S)| ≥ |S| - d for every subset S of A. We then apply Hall's theorem to the bipartite graph obtained from G by adding d new vertices to B with each of the new vertices adjacent to all vertices in A. This new graph satisfies Hall's matching condition so it admits a matching of A into B. In this matching, take A' to be the subset of A consisting of those vertices which are matched to original vertices of B. QED
The argument presented for Hall's theorem ignores computational issues, but we can use network flows to find both the least non-negative integer d = d(G) for which |N(S)| ≥ |S| - d for every subset S of A and a subset A' of A with |A'| = |A| - d for which there is a matching of A' into B.
Expand the bipartite graph G into a network flow as follows: Source s is joined to each vertex a in A by an edge of capacity 1 and each vertex in B is joined to sink t by an edge of capacity 1. For each ordered pair (a, b), assign capacity c(a, b) = 1 when a is adjacent to b in G; else set c(a, b) = 0. Then apply the labeling algorithm to find a maximum flow - with integer values. Suppose this maximum flow has value |A| - d where d ≥ 0. Then the edges of G which have flow 1 form a matching of a subset A' with |A'| = |A| - d into B. Furthermore, when the labelling algorithm halts, let S = A ∩ R and let A" = A' ∩ R. It follows immediately that N(S) = N(A") and that A - A' is a subset of S. Also, |N(A")| = |A"|, so that |N(S)| = |S| - d.
2.4 Matchings in General Graphs
Let G = (V, E) be a graph. A subset M of E is called a matching if each vertex in V is incident with at most one edge in M, and a matching is perfect if each vertex in V is incident with exactly one edge in M. A matching is maximum if no other matching contains more edges. In the following diagram, we show a perfect matching in a graph on 10 vertices.
For every subset S of V, let odd(S) denote the number of odd components in G - S. It is easy to see that if G has a perfect matching, then the following condition must hold.
Tutte's Matching Condition: |S| ≥ odd(S) for every subset S of the vertex set of G.
For example, the following graph on 18 vertices does not have a perfect matching, since removing the three red vertices leaves 5 odd components.
And of course, it turns out that the necessary condition is again sufficient.
Tutte's 1-Factor Theorem. A graph G has a perfect matching if and only if |S| ≥ odd(S) for every subset S of the vertex set of G.
In this case, we proceed immediately to formulate the defect version of Tutte's theorem and give the proof of this slightly more general result. For a graph G = (V, E), let d = d(G) be the least nonnegative integer for which the following condition holds.
Defect Matching Condition: |S| ≥ odd(S) - d for every subset S of the vertex set of G.
Here is the more general result.
Tutte's 1-Factor Theorem [Defect Form]. Let G = (V, E) be a graph G with |V| = n, and let k be a nonnegative integer. Then G has a matching M containing at least (n - k)/2 edges if and only if d(G) ≤ k.
Proof. Suppose first that G has a matching M containing at least (n - k)/2 edges. Then at most k vertices in G are not incident with any edge in M. Now let S be any subset of V. Let m = m_1 + m_2 + m_3 where m_1 edges in M have exactly one end point in S, m_2 edges in M have both endpoints in S and m_3 edges in M have neither end point in S. Also, suppose that exactly q vertices of S are not incident with an edge in E. Then odd(S) ≤ m_1 + k - q = |S| - 2m_2 + 2q + k. Thus |S| ≥ odd(S) - k. It follows that d(G) ≤ k.
On the other hand, suppose that d(G) ≤ k. We show that G has a matching containing at least (n - k)/2 edges. Clearly, we may assume that d(G) = k. It follows that there is a subset S of V for which |S| = odd(S) - k. Of all such S, take one with |S| as large as possible. Then the following facts are easily verified.
It follows from Hall's theorem that there is a matching M' in G containing |S| edges with each edge in M' having one end point in S and the other in an odd component of G - S. Furthermore, no two edges in M' have an end point in the same odd component of G - S. The desired matching in G can then be assembled by using property 1 on each even component of G - S and property 2 on C - x when C is an odd component of G - S and x is an end point of an edge in M'. QED
2.5 Factorization
An r-regular graph G is said to have a 1-factor when the edge set of G can be partitioned into r sets, each of which forms a perfect matching. For example, for each n > 1, the complete graph K_2n on 2n vertices has a 1-factor as shown in the following diagram.
The following result is an immediate corollary of Hall's theorem.
Theorem. If G = (A, B, E) is an r-regular bipartite graph and |A| = |B|, then G has a 1-factor.
Proof. We proceed by induction on r and note that it is enough to prove that G has a perfect matching. A subset S of A is incident with exactly r |S| edges. Similarly, a subset T of B is incident with exactly r |T| edges. It follows that |N(S|| ≥ |S| for every S contained in A. QED
2.6 Connectivity
Let x and y be distinct nonadjacent vertices in a graph G. Then let k(x, y) denote the fewest number of vertices whose removal from G leaves x and y in distinct components. Also, let m(x, y) denote the maximum number of pairwise disjoint paths in G from x to y (of course, the paths are allowed to have x and y in common - but no other points). Obviously, m(x, y ) never exceeds k(x, y). In the following diagram, k(x, y) = 3 as evidenced by the three blue vertices. Also, m(x, y) =3 as witnessed by the red, green and purple edges.
Consistent with the theme of this section, Menger's theorem asserts that in fact, m(x, y) is always equal to k(x, y).
Theorem [ Menger] If x and y are nonadjacent vertices in a graph G, then the minimum number k(x, y) of vertices required to separate x and y equals the maximum number m(x, y) of vertex disjoint paths from x to y.
Proof. Suppose the result is false and choose a counterexample G for which the sum of the number of vertices plus the number of edges is as small as possible. Suppose that t = k(x, y) and let S be a set of t vertices which separates x and y. Clearly, we must have t > 1. In G - S, let C(x) and C(y) denote respectively the components containing x and y. Suppose first that both C(x) and C(y) are non-trivial. Then consider the two graphs G(x) and G(y) defined as follows. In G(x), we delete all vertices in C(x) except x and make x adjacent to all vertices in S. Analogously, in G(y), we delete all vertices in C(y) except y and make y adjacent to all vertices in S. It is immediate that k(x, y) = t in both G(x) and G(y), so in both these graphs, there are t pairwise disjoint paths from x to y. The portions of paths in G(x) which belong to C(y) can be linked to the portion of the paths in G(y) which belong to C(x) to form the required paths in G.
On the other hand, if both C(x) and C(y) are trivial, then it follows that x is adjacent to every vertex in S, and thus we have our desired paths as three point paths (x, s, y) where s is in S.
So we may assume without loss of generality that C(x) is trivial while C(y) is not. Then x is adjacent to every vertex in S. If there is a vertex s in S which is also adjacent to y, then we can delete s from G and find t - 1 disjoint paths from x to y in G - s. But then the three point path (x, s, y) may be added to this collection. So we conclude that no vertex of S is adjacent to y.
Now consider a shortest path P from x to y in G. Clearly, P contains only one element of S. Label this element as s and let s' be the next vertex after s on P. If we delete the edge e = ss' from G, there is a set of size t - 1 which separates x from y. Thus S' = S - {s} + {s'} is a separating set of size t in G. And for this set, the component containing x is non-trivial, which in turn implies that the component containing y is trivial. Thus y is adjacent to all vertices in S except s, which is a contradiction. QED
There is also an edge version of the preceding result. The proof is similar.
Theorem [ Menger, Edge Version] If x and y are distinct vertices in a graph G, then the minimum number k(x, y) of edge required to separate x and y equals the maximum number m(x, y) of edge disjoint paths from x to y.
Back to Top