The maximum-flow problem is the simplest problem concerning flow networks. It asks, What is the greatest rate at which material can be shipped from the source to the sink without violating any capacity constraints? As we shall see in this chapter, this problem can be solved by efficient algorithms. Moreover, the basic techniques used by these algorithms can be adapted to solve other network-flow problems.

In this section, we give a graph-theoretic definition of flow networks, discuss their properties, and define the maximum-flow problem precisely. We also introduce some helpful notation.

A **flow network**** ***G* = (*V*, *E*) is a directed graph in which each edge (*u,v*) *E* has a nonnegative** ****capacity**** ***c*(*u, v*) 0. If (*u, v)* *E,* we assume that *c*(*u, v*) = 0. We distinguish two vertices in a flow network: a **source***s* and a **sink***t*. For convenience, we assume that every vertex lies on some path from the source to the sink. That is, for every vertex *v * *V*, there is a path . The graph is therefore connected, and |*E| * |*V*| - 1. Figure 27.1 shows an example of a flow network.

**Capacity constraint: **For all *u*, *v* *V*, we require â (*u, v) * *c*(*u, v*).

**Skew symmetry: **For all *u, v* *V*, we require â (*u, v*) = -â (*v, u*).

**Flow conservation: **For all *u* *V* - {*s*, *t*}, we require

The quantity â (*u, v*), which can be positive or negative, is called the * net flow* from vertex

for all *v* * V* - {*s, t*}. That is, the total net flow into a vertex is 0.

Our last observation concerning the flow properties deals with net flows that are positive. The * positive net flow* entering a vertex

The situation is equivalent in its result to the situation shown in Figure 27.2(d), in which 5 crates per day are shipped from *v*_{1} to *v*_{2} and no shipments are made from *v*_{2} to *v*_{1}. In effect, the 3 crates per day from *v*_{2} to *v*_{1} are **cancelled**** **by 3 of the 8 crates per day from *v*_{1} to *v*_{2}. In both situations, the net flow from *v*_{1} to *v*_{2} is 5 crates per day, but in (d), actual shipments are made in one direction only.

A maximum-flow problem may have several sources and sinks, rather than just one of each. The Lucky Puck Company, for example, might actually have a set of *m* factories {*s*_{1}*, s*_{2}, . . . ,*s _{m}*} and a set of

We can reduce the problem of determining a maximum flow in a network with multiple sources and multiple sinks to an ordinary maximum-flow problem. Figure 27.3(b) shows how the network from (a) can be converted to an ordinary flow network with only a single source and a single sink. We add a **supersource**** ***s* and add a directed edge (*s, s _{i}*) with capacity

We shall be dealing with several functions (like *f*) that take as arguments two vertices in a flow network. In this chapter, we shall use an * implicit summation notation* in which either argument, or both, may be a

Let *G *= (*V*, *E*) be a flow network, and let *f* be a flow in *G*. Then, for *X * V *,*

f(X,X) = 0 .

f(X,Y) = -f(Y,X) .

f(XY,Z) =f(X,Z) +f(Y,Z)

f(Z,XY) =f(Z,X) +f(Z,Y) .

|f|=f(V,t) .

|f| =f(s,V) (by definition)

=f(V,V) -f(V-s,V) (by Lemma 27.1)

=f(V,V- s) (by Lemma 27.1)

=f(V,t) +f(V,V-s-t) (by Lemma 27.1 )

=f(V,t) (by flow conservation) .

Later in this chapter, we shall generalize this result (Lemma 27.5).

Verify each of the three flow properties for the flow *f* shown in Figure 27.1(b).

Given a flow network *G* = (*V*, *E*), let *f*_{1} and *f*_{2} be functions from *V* X *V *to **R**. The **flow sum***f*_{1} + *f*_{2} is the function from *V* x *V *to **R** defined by

(f_{1}+f_{2})(u,v) =f_{1}(u,v) +f_{2}(u,v)

Let *f* be a flow in a network, and let be a real number. The **scalar flow product***f* is a function from *V* X *V* to **R** defined by

(f)(u,v) =f(u,v).

State the maximum-flow problem as a linear-programming problem.

The flow-network model introduced in this section supports the flow of one commodity; a * multicommodity flow network* supports the flow of

This section presents the Ford-Fulkerson method for solving the maximum-flow problem. We call it a "method" rather than an "algorithm" because it encompasses several implementations with differing running times. The Ford-Fulkerson method depends on three important ideas that transcend the method and are relevant to many flow algorithms and problems: residual networks, augmenting paths, and cuts. These ideas are essential to the important max-flow min-cut theorem (Theorem 27.7), which characterizes the value of a maximum flow in terms of cuts of the flow network. We end this section by presenting one specific implementation of the Ford-Fulkerson method and analyzing its running time.

FORD-FULKERSON-METHOD(G,s,t)

1 initialize flowfto 0

2whilethere exists an augmenting pathp

3doaugment flowfalongp

4returnf

Intuitively, given a flow network and a flow, the residual network consists of edges that can admit more net flow. More formally, suppose that we have a flow network *G* = (*V*, *E*) with source *s* and sink *t*. Let *f* be a flow in *G*, and consider a pair of vertices *u*, *v* *V*. The amount of *additional *net flow we can push from *u* to *v* before exceeding the capacity *c*(*u*, *v*) is the * residual capacity* of (

c(_{f}u,v) =c(u,v) -f(u,v) .

Given a flow network *G* = (*V*, *E*) and a flow *f*, the * residual network* of

Ef= {(u,v)VXV:c_{f}(u,v) > 0} .

That is, as promised above, each edge of the residual network, or * residual edge*, can admit a strictly positive net flow. Figure 27.4(a) repeats the flow network

|E| 2 |E| ._{f}

(f+f')(u,v) =f(u,v) +f'(u,v)

= -f(v,u) -f'(v,u)

= -(f(v,u) +f'(v,u))

= -(f+f')(v,u).

(f+f')(u,v) =f(u,v) +f'(u,v)

f(u, v) + (c(u, v) -f(u, v))

=c(u, v) .

For flow conservation, note that for all *u * *V - {s, t*}, we have

Given a flow network *G* = (*V, E*) and a flow *f*, an **augmenting path** *p* is a simple path from *s* to *t* in the residual network *G _{f}*. By the definition of the residual network, each edge (

The shaded path in Figure 27.4(b) is an augmenting path. Treating the residual network *G _{f}* in the figure as a flow network, we can ship up to 4 units of additional net flow through each edge of this path without violating a capacity constraint, since the smallest residual capacity on this path is

c(_{f}p) = min{c(_{f}u, v): (u, v) is onp}.

The following lemma, whose proof is left as Exercise 27.2-7, makes the above argument more precise.

Then, â* _{p}* is a flow in

* Proof *Immediate from Lemmas 27.2 and 27.3.

A * cut* (

â(v_{1},v_{3}) + â(v_{2},v_{3}) + â(v_{2},v_{4}) = 12 + (-4) + 11

= 19,

c(v_{l},v_{3}) +c(v_{2},v_{4}) = 12 + 14

= 26.

* Proof *Using Lemma 27.1 extensively, we have

â(S,T) = â(S,V) - â(S,S)

= â(S,V)

= â(s,V) + â(S-s,V)

= â(s,V)

= | â | .

Another corollary to Lemma 27.5 shows how cut capacities can be used to bound the value of a flow.

The value of any flow â in a flow network *G* is bounded from above by the capacity of any cut of *G*.

* Proof *Let (

|â| =â(S,T)

We are now ready to prove the important max-flow min-cut theorem.

If â is a flow in a flow network *G* = (*V*, *E*) with source *s* and sink *t*, then the following conditions are equivalent:

2. The residual network *G*_{â} contains no augmenting paths.

3. | â | = *c*(*S*, *T*) for some cut (*S*, *T*) of *G*.

*S* = {*v* *V *: there exists a path from *s* to in *G*_{â}}

FORD-FULKERSON(G,s,t)

1foreach edge (u,v)E[G]

2doâ[u,v] 0

3â[v,u] 0

4whilethere exists a pathpfromstotin the residual networkG_{â}

5doc_{â}(p) min {c_{â}(u,v) : (u,v) is inp}

6foreach edge (u,v) inp

7doâ[u,v]â[u,v]+c_{â}(p)

8â[v,u] -â[u,v]

The bound on FORD-FULKERSON can be improved if we implement the computation of the augmenting path *p* in line 4 with a breadth-first search, that is, if the augmenting path is a *shortest* path from *s* to *t* in the residual network, where each edge has unit distance (weight). We call the Ford-Fulkerson method so implemented the * Edmonds-Karp algorithm.* We now prove that the Edmonds-Karp algorithm runs in

_{}'_{(s, v) < }_{}(s,v).

_{}'_{(s, u) < }s_{'}(,v) implies_{}_{(s, u) }s, u_{'}().

s, u_{}_{(})_{'}(s, u) .

s_{}_{(},v)_{}(s, u) + 1 (by Lemma 25.3)

'_{}s_{(},u) + 1

='_{}s_{(},v) ,

which contradicts our assumption that the flow augmentation decreases the distance from *s* to *v*.

s_{}_{(},v) =_{}(s,u) - 1

_{}_{}'s, u_{(}) - 1

='(s,v) - 2

<'(s,v) ,

which contradicts our initial assumption.

The next theorem bounds the number of iterations of the Edmonds-Karp algorithm.

* Proof *We say that an edge (

s_{}_{(},v) =_{}(s,u) + 1 .

'(s, u) ='(s,v) + 1.

Since * _{(}*s

'(s,u) = '(s,v) + 1

(s,v) + 1

= (s,u) + 2.

Show the execution of the Edmonds-Karp algorithm on the flow network of Figure 27.1(a).

The * edge connectivity* of an undirected graph is the minimum number

Some combinatorial problems can easily be cast as maximum-flow problems. The multiple-source, multiple-sink maximum-flow problem from Section 27.1 gave us one example. There are other combinatorial problems that seem on the surface to have little to do with flow networks, but can in fact be reduced to a maximum-flow problem. This section presents one such problem: finding a maximum matching in a bipartite graph (see Section 5.4). In order to solve this problem, we shall take advantage of an integrality property provided by the Ford-Fulkerson method. We shall also see that the Ford-Fulkerson method can be made to solve the maximum-bipartite-matching problem on a graph *G = (V, E*) in *O(V E)* time.

Given an undirected graph *G = *(*V, E*), a * matching* is a subset of edges

We can use the Ford-Fulkerson method to find a maximum matching in an undirected bipartite graph* G = *(*V, E*)* *in time polynomial in |*V*| and |*E*|. The trick is to construct a flow network in which flows correspond to matchings, as shown in Figure 27.9. We define the **corresponding flow network*** G*' = (*V*'*, E*') for the bipartite graph* G* as follows. We let the sources *s* and sink *t* be new vertices not in *V*, and we let* V**'= V * {*s, t*}. If the vertex partition of *G* is *V *=* L* *R*, the directed edges of* G**' *are given by

E' = {(s,u):uL}

{(u,v):uL,vR, and (u,v)E}

{(v,t):vR} .

To complete the construction, we assign unit capacity to each edge in *E*'.

The following theorem shows that a maching in *G* corresponds directly to a flow in* G*'s corresponding flow network *G**'*. We say that a flow on a flow network *G = *(*V, E*) is * integer-valued* if (

To prove the converse, let *f *be an integer-valued flow in *G*' and let

M= {(u,v):uL,vR, andf(u, v)> 0} .

|M| =â(L,R)

=â(L,V') -â(L,L) -â(L,s) -â(L,t)

= 0 - 0 +â(s,L) - 0

=â(s,V')

= |â| .

If the capacity function *c* takes on only integral values, then the maximum flow â produced by the Ford-Fulkerson method has the property that |â| is integer-valued. Moreover, for all vertices *u* and *v*, the value of â(*u, v*) is an integer.

* Proof *The proof is by induction on the number of iterations. We leave it as Exercise 27.3-2.

We can now prove the following corollary to Lemma 27.10.

A * perfect matching *is a matching in which every vertex is matched. Let

N(X)={yV:(x, y)Efor somexX},

A bipartite graph *G* = (*V*,* E*), where *V = L* *R*, is * d-regular* if every vertex

In this section, we present the "preflow-push" approach to computing maximum flows. The fastest maximum-flow algorithms to date are preflow-push algorithms, and other flow problems, such as the minimum-cost flow problem, can be solved efficiently by preflow-push methods. This section introduces Goldberg's "generic" maximum-flow algorithm, which has a simple implementation that runs in *O*(*V*^{2}* E*) time, thereby improving upon the *O*(*V E*^{2}) bound of the Edmonds-Karp algorithm. Section 27.5 refines the generic algorithm to obtain another preflow-push algorithm that runs in* O*(*V*^{3}) time*.*

Preflow-push algorithms work in a more localized manner than the Ford-Fulkerson method. Rather than examine the entire residual network *G =* (*V, E*) to find an augmenting path, preflow-push algorithms work on one vertex at a time, looking only at the vertex's neighbors in the residual network. Furthermore, unlike the Ford-Fulkerson method, preflow-push algorithms do not maintain the flow-conservation property throughout their execution. They do, however, maintain a* preflow*, which is a function

e(u)= f(V, u) .

We say that a vertex u V - {s, t} is **overflowing** if e(u) > 0.

From the preceding discussion, we see that there are two basic operations performed by a preflow-push algorithm: pushing flow excess from a vertex to one of its neighbors and lifting a vertex. The applicability of these operations depends on the heights of vertices, which we now define precisely.

Let *G* = (*V, E*) be a flow network with source *s* and sink *t*, and let* f* be a preflow in *G*. A function *h: V* **N** is a **height function*** *if *h*(*s*) = |*V*|,

h(t) = 0, and

h(u)h(v) + 1

for every residual edge (*u, v*) *E _{f}* . We immediately obtain the following lemma.

PUSH(u, v)

1Applies when:uis overflowing,c[_{f}u, v] > 0, andh[u]= h[v] + 1.

2Action:Pushd(_{f}u, v) = min(e[u], c(_{f}u, v)) units of flow

fromutov.

3d(_{f}u, v) min(e[u], c(_{f}u, v))

4f[u, v]f[u, v]+d(_{f}u, v)

5f[v, u]- f[u, v]

6e[u]e[u]-_{}(u, v)

7e[v]e[v]+ d(_{f}u, v)

We call the operation PUSH(*u, v*) a * push* from

The basic operation LIFT(*u*) applies if *u* is overflowing and if *c _{f} *(

LIFT(u)

1Applies when:uis overflowing and for allvV,

(u, v)E_{f}impliesh[u]h[v].

2Action:Increase the height ofu.

3h[u] 1 + min {h[v]: (u, v)E_{f}}

c_{â}(u,v) =c(u,v) -f[u,v]

=c(u,v) +f[v,u]

> 0,

The generic preflow-push algorithm uses the following subroutine to create an initial preflow in the flow network.

INITIALIZE-PREFLOW(G,s)

1foreach vertexuV[G]

2doh[u] 0

3e[u]0

4foreach edge (u,v)E[G]

5doâ[u,v] 0

6â[v,u] 0

7h[s] |V[G]|

8foreach vertexuAdj[s]

9doâ[s,u]c(s,u)

10â[u,s] -c(s,u)

11e[u]c(s,u)

INITIALIZE-PREFLOW creates an initial preflowâdefined by

The following algorithm typifies the preflow-push method.

GENERIC-PREFLOW-PUSH(G)

1 INITIALIZE-PREFLOW(G,s)

2whilethere exists an applicable push or lift operation

3doselect an applicable push or lift operation and perform it

The following lemma gives an important property of height functions.

Let *G* = (*V*, *E*) be a flow network with source *s* and sink *t*. Then, during the execution of GENERIC-PREFLOW-PUSH on *G*, the number of lift operations is at most 2 |*V*| - 1 per vertex and at most (2 |*V*| - 1)(|*V*| - 2) < 2 |*V* |^{2 }overall.

Lemma 27.20 also helps us to bound the number of saturating pushes.

The following lemma bounds the number of nonsaturating pushes in the generic preflow-push algorithm.

* Proof *Immediate from Corollary 27.21 and Lemmas 27.22 and 27.23.

Give an efficient preflow-push algorithm to find a maximum matching in a bipartite graph. Analyze your algorithm.

Show that line 7 of INITIALIZE-PREFLOW can be changed to

h[s]V[G] - 2

without affecting the correctness or asymptotic performance of the generic preflow-push algorithm.

The preflow-push method allows us to apply the basic operations in any order at all. By choosing the order carefully and managing the network data structure efficiently, however, we can solve the maximum-flow problem faster than the* O*(*V ^{2}E*) bound given by Corollary 27.25. We shall now examine the lift-to-front algorithm, a preflow-push algorithm whose running time is

If *G = *(*V, E*)* *is a flow network with source *s* and sink *t,* _{ }is a preflow in *G,* and* h *is a height function, then we say that* *(*u,v*)* *is an* admissible edge* if

The next two lemmas show how push and lift operations change the admissible network.

Edges in the lift-to-front algorithm are organized into "neighbor lists." Given a flow network* G =* (*V,E*)*,* the** neighbor list ***N*[*u*]* *for a vertex* u ** V *is a singly linked list of the neighbors of *u *in* G*. Thus, vertex appears in the list *N*[*u*]* *if (*u,*) * E *or* (**,u*)* ** E. *The neighbor list *N*[*u*] contains exactly those vertices * *for which there* *may be a residual edge (*u,*)*.* The first vertex in *N*[*u*]* *is pointed to by *head *[*N*[*u*]]*.* The vertex following* ** *in* a *neighbor list is pointed to by *next-neighbor*[]*; *this pointer is NIL if* * is the last vertex in the neighbor list.

An overflowing vertex *u* is * discharged *by pushing all of its excess flow through admissible edges to neighboring vertices, lifting

DISCHARGE(u)

1whilee[u] > 0

2docurrent[u]

3if= NIL

4thenLIFT(u)

5current[u]head[N[u]]

6elseifc_{(u,)}> 0 andh[u] =h[] + 1

7thenPUSH(u,)

8elsecurrent[u]next-neighbor[]

LIFT-TO-FRONT(G,s,t)

1 INITIALIZE-PREFLOW(G,s)

2LV[G] - {s,t}, in any order

3foreach vertexuV[G] - {s,t}

4docurrent[u]head[N[u]]

5uhead[L]

6whileuNIL

7doold-heighth[u]

8 DISCHARGE(u)

9ifh[u] >old-height

10thenmoveuto the front of listL

11unext[u]

The running time of LIFT-TO-FRONT on any flow network *G *= (*V*, *E*) is *O*(*V*^{3}).

The running time of LIFT-TO-FRONT is therefore *O*(*V*^{3} + *V E*), which is *O(V*^{3}).

N[v_{1}] = s,v_{2},v_{3},

N[v_{2}] = s,v_{1},v_{3},v_{4},

N[v_{3}] =v_{1},v_{2},v_{4},t,

N[v_{4}] =v_{2},v_{3},t.

We would like to implement a preflow-push algorithm in which we maintain a first-in, first-out queue of overflowing vertices. The algorithm repeatedly discharges the vertex at the head of the queue, and any vertices that were not overflowing before the discharge but are overflowing afterward are placed at the end of the queue. After the vertex at the head of the queue is discharged, it is removed. When the queue is empty, the algorithm terminates. Show that this algorithm can be implemented to compute a maximum flow in *O*(*V*^{3}) time.

An *n *x* n grid* is an undirected graph consisting of

* b*. Describe an efficient algorithm to solve the escape problem, and analyze its running time.

A * path cover* of a directed graph

V' = {x_{0},x_{1}, . . . ,x_{n}} {y_{0, }y_{1}, . . . ,y_{n}} ,

E' = {(x_{0},x_{i}) :iV} {(y_{i},_{ }y_{0}) :iV} {(x_{i},y_{j}) : (i,j)E} ,

and run a maximum-flow algorithm.)

**b****.** Does your algorithm work for directed graphs that contain cycles? Explain.

27-3 Space shuttle experiments

**a.**** **Show that if *E _{j}*

Let *G = *(*V, E*) be a flow network with source *s*, sink *t*, and integer capacities. Suppose that we are given a maximum flow in *G.*

Let *G = *(*V, E*) be a flow network with source *s*, sink *t*, and an integer capacity *c(u, v*) on each edge (*u, v) *_{ }E* _{. Let }*C =

* a*. Argue that a minimum cut of

The following modification of FORD-FULKERSON-METHOD can be used to compute a maximum flow in *G*.

MAX-FLOW-BY-SCALING(G, s, t)

1Cmax_{(u,v)}E(_{c}u, v)

2 initialize flowfto 0

3K2C^{}1g^{}

4whileK1

5do whilethere exists an augmenting pathpof capacity at leastK

6doaugment flowfalongp

7KK/2

8returnf

* c*. Argue that MAX-FLOW-BY-SCALING returns a maximum flow.

* e*. Argue that the inner

* f*. Conclude that MAX-FLOW-BY-SCALING can be implemented to run in

27-6 Maximum flow with upper and lower capacity bounds

Suppose that each edge (*u, v*) in a flow network *G* = (*V, E*) has not only an upper bound *c*(*u, v*) on the net flow from *u* to *v*, but also a lower bound *b*(*u, v*). That is, any flow *f* on the network must satisfy *b*(*u, v*) *f*(*u, v*) *c*(*u, v*). It may be the case for such a network that no feasible flow exists.

**a****.** Prove that if *f* is a flow on *G*, then |*f*| *c*(*S, T*) - *b*(*T, S*) for any cut (*S, T*) of *G.*

V' =V{s',t'} ,

E' =E{(s',v) :vV} {(u,t') :uV} {(s,t),(t,s)} .

The Ford-Fulkerson method is due to Ford and Fulkerson [71], who originated many of the problems in the area of network flow, including the maximum-flow and bipartite-matching problems. Many early implementations of the Ford-Fulkerson method found augmenting paths using breadth-first search; Edmonds and Karp [63] proved that this strategy yields a polynomial-time algorithm. Karzanov [119] developed the idea of preflows. The preflow-push method is due to Goldberg [82]. The fastest preflow-push algorithm to date is due to Goldberg and Tarjan [85], who achieve a running time of *O(V E *lg(*V ^{2}/E*)). The best algorithm to date for maximum bipartite matching, discovered by Hopcroft and Karp [101], runs in time.