7.2 Flows in networks

7.2.1 Shipping oil

Figure 7.4( $a$ ) shows a directed graph representing a network of pipelines along which oil can be sent. The goal is to ship as much oil as possible from the source s to the sink t. Each pipeline has a maximum capacity it can handle, and there are no opportunities for storing oil en route. Figure 7.4( $b$ ) shows a possible flow from s to t, which ships 7 units in all. Is this the best that can be done?

7.2.2 Maximizing flow

The networks we are dealing with consist of a directed graph $G = ( V , E )$ ; two special nodes $s , t \in V$ , which are, respectively, a source and sink of $G ;$ and capacities $c _ { e } > 0$ on the edges.

We would like to send as much oil as possible from s to t without exceeding the capacities of any of the edges. A particular shipping scheme is called a flow and consists of a variable $f _ { e }$ for each edge e of the network, satisfying the following two properties:

It doesn’t violate edge capacities: $0 \leq f _ { e } \leq c _ { e }$ for all $e \in E .$
For all nodes u except s and $t ,$ the amount of flow entering u equals the amount leaving

Figure 7.4 ( $a$ ) A network with edge capacities. ( $b$ ) A flow in the network.

$u$ :

\sum_ {(w, u) \in E} f _ {w u} = \sum_ {(u, z) \in E} f _ {u z}.

In other words, flow is conserved.

The size of a flow is the total quantity sent from s to t and, by the conservation principle, is equal to the quantity leaving s:

\operatorname{size} (f) = \sum_ {(s, u) \in E} f _ {s u}.

In short, our goal is to assign values to $\{ f _ { e } : e \in E \}$ that will satisfy a set of linear constraints and maximize a linear objective function. But this is a linear program! The maximum-flow problem reduces to linear programming.

For example, for the network of Figure 7.4 the LP has 11 variables, one per edge. It seeks to maximize $f _ { s a } + f _ { s b } + f _ { s c }$ subject to a total of 27 constraints: 11 for nonnegativity (such as $f _ { s a } \geq 0 )$ , 11 for capacity (such as $f _ { s a } \leq 3 )$ , and 5 for flow conservation (one for each node of the graph other than s and $t ,$ such as $f _ { s c } + f _ { d c } = f _ { c e } )$ . Simplex would take no time at all to correctly solve the problem and to confirm that, in our example, a flow of 7 is in fact optimal.

7.2.3 A closer look at the algorithm

All we know so far of the simplex algorithm is the vague geometric intuition that it keeps making local moves on the surface of a convex feasible region, successively improving the objective function until it finally reaches the optimal solution. Once we have studied it in more detail (Section 7.6), we will be in a position to understand exactly how it handles flow LPs, which is useful as a source of inspiration for designing direct max-flow algorithms.

It turns out that in fact the behavior of simplex has an elementary interpretation:

Start with zero flow.

Repeat: choose an appropriate path from s to t, and increase flow along the edges of this path as much as possible.

Figure 7.5( $a$ )–( $d$ ) shows a small example in which simplex halts after two iterations. The final flow has size 2, which is easily seen to be optimal.

Figure 7.5 An illustration of the max-flow algorithm. ( $a$ ) A toy network. ( $b$ ) The first path chosen. ( $c$ ) The second path chosen. ( $d$ ) The final flow. ( $e$ ) We could have chosen this path first. ( $f$ ) In which case, we would have to allow this second path.

( $a$ )

( $b$ )

( $c$ )

( $d$ )

( $e$ )

( $f$ )

There is just one complication. What if we had initially chosen a different path, the one in Figure 7.5( $e$ )? This gives only one unit of flow and yet seems to block all other paths. Simplex gets around this problem by also allowing paths to cancel existing flow. In this particular case, it would subsequently choose the path of Figure 7.5( $f$ ). Edge $( b , a )$ of this path isn’t in the original network and has the effect of canceling flow previously assigned to edge $( a , b )$

To summarize, in each iteration simplex looks for an $s - t$ path whose edges $( u , v )$ can be of two types:

$( u , v )$ is in the original network, and is not yet at full capacity.
The reverse edge $( v , u )$ is in the original network, and there is some flow along it.

If the current flow is $f ,$ then in the first case, edge $( u , v )$ can handle up to $c _ { u v } - f _ { u v }$ additional units of flow, and in the second case, upto $f _ { v u }$ additional units (canceling all or part of the existing flow on $( v , u ) )$ . These flow-increasing opportunities can be captured in a residual network $G ^ { f } = ( V , E ^ { f } )$ , which has exactly the two types of edges listed, with residual capacities

cf:

\left\{ \begin{array}{c l} c _ {u v} - f _ {u v} & \textbf {i f} (u, v) \in E \textbf {a n d} f _ {u v} < c _ {u v} \\ f _ {v u} & \textbf {i f} (v, u) \in E \textbf {a n d} f _ {v u} > 0 \end{array} \right.

Thus we can equivalently think of simplex as choosing an $s - t$ path in the residual network.

By simulating the behavior of simplex, we get a direct algorithm for solving max-flow. It proceeds in iterations, each time explicitly constructing $G ^ { f }$ , finding a suitable $s - t$ path in $G ^ { f }$ by using, say, a linear-time breadth-first search, and halting if there is no longer any such path along which flow can be increased.

Figure 7.6 illustrates the algorithm on our oil example.

7.2.4 A certificate of optimality

Now for a truly remarkable fact: not only does simplex correctly compute a maximum flow, but it also generates a short proof of the optimality of this flow!

Let’s see an example of what this means. Partition the nodes of the oil network (Figure 7.4) into two groups, $L = \{ s , a , b \}$ and $R = \{ c , d , e , t \}$ :

Any oil transmitted must pass from L to R. Therefore, no flow can possibly exceed the total capacity of the edges from L to $R ,$ which is 7. But this means that the flow we found earlier, of size 7, must be optimal!

More generally, an $( s , t ) – c u t$ partitions the vertices into two disjoint groups L and R such that s is in L and t is in R. Its capacity is the total capacity of the edges from $L$ to $R ,$ and as argued previously, is an upper bound on any flow:

Pick any flow f and any ( $s$ , $t$ )-cut ( $L$ , $R$ ). Then size $( f ) \ \leq$ capacity( $L$ , $R$ ).

Some cuts are large and give loose upper bounds—cut $( \{ s , b , c \} , \{ a , d , e , t \} )$ has a capacity of 19. But there is also a cut of capacity 7, which is effectively a certificate of optimality of the maximum flow. This isn’t just a lucky property of our oil network; such a cut always exists.

Max-flow min-cut theorem The size ofthe maximum flow in a network equals the capacity of the smallest $( s , t ) \ – c u t .$

Moreover, our algorithm automatically finds this cut as a by-product!

Let’s see why this is true. Suppose f is the final flow when the algorithm terminates. We know that node t is no longer reachable from s in the residual network $G ^ { f }$ . Let L be the nodes that are reachable from s in $G ^ { f }$ , and let $R = V - L$ be the rest of the nodes. Then $( L , R )$ is a cut in the graph G:

We claim that

\operatorname{size} (f) = \operatorname{capacity} (L, R).

To see this, observe that by the way L is defined, any edge going from L to $R$ must be at full capacity (in the current flow $f ) _ { - }$ , and any edge from $R$ to $L$ must have zero flow. $( \mathbf { S } \mathbf { 0 } ,$ in the figure, $f _ { e } = c _ { e }$ and $f _ { e ^ { \prime } } = 0 . )$ Therefore the net flow across $( L , R )$ is exactly the capacity of the cut.

7.2.5 Efficiency

Each iteration of our maximum-flow algorithm is efficient, requiring $O ( | E | )$ time if a depthfirst or breadth-first search is used to find an $s - t$ path. But how many iterations are there?

Suppose all edges in the original network have integer capacities $\le C$ . Then an inductive argument shows that on each iteration of the algorithm, the flow is always an integer and increases by an integer amount. Therefore, since the maximum flow is at most $C | E |$ (why?), it follows that the number of iterations is at most this much. But this is hardly a reassuring bound: what if C is in the millions?

We examine this issue further in Exercise7.31. It turns out that it is indeed possible to construct bad examples in which the number of iterations is proportional to $C , i f s - t$ paths are not carefully chosen. However, if paths are chosen in a sensible manner—in particular, by using a breadth-first search, which finds the path with the fewest edges—then the number of iterations is at most $O ( | V | \cdot | E | )$ , no matter what the capacities are. This latter bound gives an overall running time of $O ( | V | \cdot | E | ^ { 2 } )$ for maximum flow.

Figure 7.6 The max-flow algorithm applied to the network of Figure 7.4. At each iteration, the current flow is shown on the left and the residual network on the right. The paths chosen are shown in bold.

Current flow

Residual graph