Home | | Design and Analysis of Algorithms | The Iterative Maximum-Flow Problem

# The Iterative Maximum-Flow Problem

In this section, we consider the important problem of maximizing the flow of a ma-terial through a transportation network (pipeline system, communication system, electrical distribution system, and so on).

The Maximum-Flow Problem

In this section, we consider the important problem of maximizing the flow of a ma-terial through a transportation network (pipeline system, communication system, electrical distribution system, and so on). We will assume that the transportation network in question can be represented by a connected weighted digraph with n vertices numbered from 1 to n and a set of edges E, with the following properties:

It contains exactly one vertex with no entering edges; this vertex is called the source and assumed to be numbered 1.

It contains exactly one vertex with no leaving edges; this vertex is called the sink and assumed to be numbered n.

The weight uij of each directed edge (i, j ) is a positive integer, called the edge capacity. (This number represents the upper bound on the amount of the material that can be sent from i to j through a link represented by this edge.)

A digraph satisfying these properties is called a flow network or simply a network.3 A small instance of a network is given in Figure 10.4.

It is assumed that the source and the sink are the only source and destination of the material, respectively; all the other vertices can serve only as points where a flow can be redirected without consuming or adding any amount of the material. In other words, the total amount of the material entering an intermediate vertex must be equal to the total amount of the material leaving the vertex. This con-dition is called the flow-conservation requirement. If we denote the amount sent through edge (i, j ) by xij , then for any intermediate vertex i, the flow-conservation requirement can be expressed by the following equality constraint: where the sums in the left- and right-hand sides express the total inflow and outflow entering and leaving vertex i, respectively.

Since no amount of the material can change by going through intermediate vertices of the network, it stands to reason that the total amount of the material leaving the source must end up at the sink. (This observation can also be derived formally from equalities (10.8), a task you will be asked to do in the exercises.) Thus, we have the following equality: This quantity, the total outflow from the source—or, equivalently, the total inflow into the sink—is called the value of the flow. We denote it by v. It is this quantity that we will want to maximize over all possible flows in a network.

Thus, a (feasible) flow is an assignment of real numbers xij to edges (i, j ) of a given network that satisfy flow-conservation constraints (10.8) and the capacity constraints The maximum-flow problem can be stated formally as the following optimization problem: We can solve linear programming problem (10.11) by the simplex method or by another algorithm for general linear programming problems (see Section 10.1). However, the special structure of problem (10.11) can be exploited to design faster algorithms. In particular, it is quite natural to employ the iterative-improvement idea as follows. We can always start with the zero flow (i.e., set xij = 0 for every edge (i, j ) in the network). Then, on each iteration, we can try to find a path from source to sink along which some additional flow can be sent. Such a path is called flow augmenting. If a flow-augmenting path is found, we adjust the flow along the edges of this path to get a flow of an increased value and try to find an augmenting path for the new flow. If no flow-augmenting path can be found, we conclude that the current flow is optimal. This general template for solving the maximum-flow problem is called the augmenting-path method, also known as the Ford-Fulkerson method after L. R. Ford, Jr., and D. R. Fulkerson, who discovered it (see [For57]).

An actual implementation of the augmenting path idea is, however, not quite straightforward. To see this, let us consider the network in Figure 10.4. We start with the zero flow shown in Figure 10.5a. (In that figure, the zero amounts sent through each edge are separated from the edge capacities by the slashes; we will use this notation in the other examples as well.) It is natural to search for a flow-augmenting path from source to sink by following directed edges (i, j ) for which the current flow xij is less than the edge capacity uij . Among several possibilities, let us assume that we identify the augmenting path 1236 first. We can increase the flow along this path by a maximum of 2 units, which is the smallest unused capacity of its edges. The new flow is shown in Figure 10.5b. This is as far as our simpleminded idea about flow-augmenting paths will be able to take us. Unfortunately, the flow shown in Figure 10.5b is not optimal: its value can still be increased along the path 143256 by increasing the flow by 1 on edges (1, 4), (4, 3), (2, 5), and (5, 6) and decreasing it by 1 on edge (2, 3). The flow obtained as the result of this augmentation is shown in Figure 10.5c. It is indeed maximal. (Can you tell why?)

Thus, to find a flow-augmenting path for a flow x, we need to consider paths from source to sink in the underlying undirected graph in which any two consec-utive vertices i, j are either

connected by a directed edge from i to j with some positive unused capacity rij = uij xij (so that we can increase the flow through that edge by up to rij units), or

connected by a directed edge from j to i with some positive flow xj i (so that we can decrease the flow through that edge by up to xj i units).

Edges of the first kind are called forward edges because their tail is listed before their head in the vertex list 1 . . . i j . . . n defining the path; edges of the second kind are called backward edges because their tail is listed after their head in the path list 1 . . . i j . . . n. To illustrate, for the path 143256 of the last example, (1, 4), (4, 3), (2, 5), and (5, 6) are the forward edges, and (3, 2) is the backward edge.

For a given flow-augmenting path, let r be the minimum of all the unused capacities rij of its forward edges and all the flows xj i of its backward edges. It is easy to see that if we increase the current flow by r on each forward edge and decrease it by this amount on each backward edge, we will obtain a feasible  flow whose value is r units greater than the value of its predecessor. Indeed, let i be an intermediate vertex on a flow-augmenting path. There are four possible combinations of forward and backward edges incident to vertex i: For each of them, the flow-conservation requirement for vertex i will still hold after the flow adjustments indicated above the edge arrows. Further, since r is the minimum among all the positive unused capacities on the forward edges and all the positive flows on the backward edges of the flow-augmenting path, the new flow will satisfy the capacity constraints as well. Finally, adding r to the flow on the first edge of the augmenting path will increase the value of the flow by r.

Under the assumption that all the edge capacities are integers, r will be a positive integer too. Hence, the flow value increases at least by 1 on each iteration of the augmenting-path method. Since the value of a maximum flow is bounded above (e.g., by the sum of the capacities of the source edges), the augmenting-path method has to stop after a finite number of iterations.4 Surprisingly, the final flow always turns out to be maximal, irrespective of a sequence of augmenting paths. This remarkable result stems from the proof of the Max-Flow Min-Cut Theorem (see, e.g., [For62]), which we replicate later in this section.

The augmenting-path method—as described above in its general form—does not indicate a specific way for generating flow-augmenting paths. A bad sequence of such paths may, however, have a dramatic impact on the method’s efficiency. Consider, for example, the network in Figure 10.6a, in which U stands for some large positive integer. If we augment the zero flow along the path 1234, we shall obtain the flow of value 1 shown in Figure 10.6b. Augmenting that flow along the path 1324 will increase the flow value to 2 (Figure 10.6c). If we continue selecting this pair of flow-augmenting paths, we will need a total of 2U iterations to reach the maximum flow of value 2U (Figure 10.6d). Of course, we can obtain the maximum flow in just two iterations by augmenting the initial zero flow along the path 124 followed by augmenting the new flow along the path 134. The dramatic difference between 2U and 2 iterations makes the point.

Fortunately, there are several ways to generate flow-augmenting paths ef-ficiently and avoid the degradation in performance illustrated by the previous example. The simplest of them uses breadth-first search to generate augment-ing paths with the least number of edges (see Section 3.5). This version of the augmenting-path method, called shortest-augmenting-path or first-labeled-first-scanned algorithm, was suggested by J. Edmonds and R. M. Karp [Edm72]. The labeling refers to marking a new (unlabeled) vertex with two labels. The first label indicates the amount of additional flow that can be brought from the source to the vertex being labeled. The second label is the name of the vertex from which the vertex being labeled was reached. (It can be left undefined for the source.) It is also convenient to add the + or sign to the second label to indicate whether the vertex was reached via a forward or backward edge, respectively. The source can be always labeled with , . For the other vertices, the labels are computed as follows. If unlabeled vertex j is connected to the front vertex i of the traversal queue by a directed edge from i to j with positive unused capacity rij = uij xij , then

vertex j is labeled with lj , i+, where lj = min{li, rij }.

If unlabeled vertex j is connected to the front vertex i of the traversal queue by a directed edge from j to i with positive flow xj i, then vertex j is labeled with

lj , i, where lj = min{li, xj i}.

If this labeling-enhanced traversal ends up labeling the sink, the current flow can be augmented by the amount indicated by the sink’s first label. The augmentation is performed along the augmenting path traced by following the vertex second labels from sink to source: the current flow quantities are increased on the forward edges and decreased on the backward edges of this path. If, on the other hand, the sink remains unlabeled after the traversal queue becomes empty, the algorithm returns the current flow as maximum and stops.

ALGORITHM                 ShortestAugmentingPath(G)

//Implements the shortest-augmenting-path algorithm //Input: A network with single source 1, single sink n, and // positive integer capacities uij on its edges (i, j ) //Output: A maximum flow x

assign xij = 0 to every edge (i, j ) in the network

label the source with , and add the source to the empty queue Q     capacities of the edges that compose the cut. For the three examples of cuts given above, the capacities are equal to 5, 6, and 9, respectively. Since the number of different cuts in a network is nonempty and finite (why?), there always exists a minimum cut, i.e., a cut with the smallest capacity. (What is a minimum cut in the network of Figure 10.4?) The following theorem establishes an important relationship between the notions of maximum flow and minimum cut.

THEOREM (Max-Flow Min-Cut Theorem) The value of a maximum flow in a network is equal to the capacity of its minimum cut. Thus, the value of any feasible flow in a network cannot exceed the capacity of any cut in that network.

Let v be the value of a final flow x obtained by the augmenting-path method. If we now find a cut whose capacity is equal to v, we will have to conclude, in view of inequality (10.13), that (i) the value v of the final flow is maximal among all feasible flows, (ii) the cut’s capacity is minimal among all cuts in the network, and

the maximum-flow value is equal to the minimum-cut capacity.

To find such a cut, consider the set of vertices X that can be reached from the

source by following an undirected path composed of forward edges with positive unused capacities (with respect to the final flow x) and backward edges with positive flows on them. This set contains the source but does not contain the sink: if it did, we would have an augmenting path for the flow x, which would The proof outlined above accomplishes more than proving the equality of the maximum-flow value and the minimum-cut capacity. It also implies that when the augmenting-path method terminates, it yields both a maximum flow and a mini-mum cut. If labeling of the kind utilized in the shortest-augmenting-path algorithm is used, a minimum cut is formed by the edges from the labeled to unlabeled ver-tices on the last iteration of the method. Finally, the proof implies that all such edges must be full (i.e., the flows must be equal to the edge capacities), and all the edges from unlabeled vertices to labeled, if any, must be empty (i.e., have zero flows on them). In particular, for the network in Figure 10.7, the algorithm finds the cut {(1, 2), (4, 3)} of minimum capacity 3, both edges of which are full as required.

Edmonds and Karp proved in their paper [Edm72] that the number of aug-menting paths needed by the shortest-augmenting-path algorithm never exceeds nm/2, where n and m are the number of vertices and edges, respectively. Since the time required to find a shortest augmenting path by breadth-first search is in O(n + m) = O(m) for networks represented by their adjacency lists, the time efficiency of the shortest-augmenting-path algorithm is in O(nm2).

More efficient algorithms for the maximum-flow problem are known (see the monograph [Ahu93], as well as appropriate chapters in such books as [Cor09] and [Kle06]). Some of them implement the augmenting-path idea in a more efficient manner. Others are based on the concept of preflows. A preflow is a flow that satisfies the capacity constraints but not the flow-conservation requirement. Any vertex is allowed to have more flow entering the vertex than leaving it. A preflow-push algorithm moves the excess flow toward the sink until the flow-conservation requirement is reestablished for all intermediate vertices of the network. Faster al-gorithms of this kind have worst-case efficiency close to O(nm). Note that preflow-push algorithms fall outside the iterative-improvement paradigm because they do not generate a sequence of improving solutions that satisfy all the constraints of the problem.

To conclude this section, it is worth pointing out that although the initial interest in studying network flows was caused by transportation applications, this model has also proved to be useful for many other areas. We discuss one of them in the next section.

Exercises 10.2

Since maximum-flow algorithms require processing edges in both directions, it is convenient to modify the adjacency matrix representation of a network as follows. If there is a directed edge from vertex i to vertex j of capacity uij , then the element in the ith row and the j th column is set to uij , and the element in the j th row and the ith column is set to uij ; if there is no edge between vertices i and j , both these elements are set to zero. Outline a simple algorithm for identifying a source and a sink in a network presented by such a matrix and indicate its time efficiency.

Apply the shortest-augmenting path algorithm to find a maximum flow and a minimum cut in the following networks. a. Does the maximum-flow problem always have a unique solution? Would your answer be different for networks with different capacities on all their edges?

Answer the same questions for the minimum-cut problem of finding a cut of the smallest capacity in a given network.

a. Explain how the maximum-flow problem for a network with several sources and sinks can be transformed into the same problem for a network with a single source and a single sink.

Some networks have capacity constraints on the flow amounts that can flow through their intermediate vertices. Explain how the maximum-flow problem for such a network can be transformed to the maximum-flow problem for a network with edge capacity constraints only.

Consider a network that is a rooted tree, with the root as its source, the leaves as its sinks, and all the edges directed along the paths from the root to the leaves. Design an efficient algorithm for finding a maximum flow in such a network. What is the time efficiency of your algorithm?

a.  Prove equality (10.9).

Prove that for any flow in a network and any cut in it, the value of the flow is equal to the flow across the cut (see equality (10.12)). Explain the relationship between this property and equality (10.9).

a. Express the maximum-flow problem for the network in Figure 10.4 as a linear programming problem.

Solve this linear programming problem by the simplex method.

As an alternative to the shortest-augmenting-path algorithm, Edmonds and Karp [Edm72] suggested the maximum-capacity-augmenting-path algorithm, in which a flow is augmented along the path that increases the flow by the largest amount. Implement both these algorithms in the language of your choice and perform an empirical investigation of their relative efficiency.

Write  a  report  on  a  more  advanced  maximum-flow  algorithm  such  as

(i) Dinitz’s algorithm, (ii) Karzanov’s algorithm, (iii) Malhotra-Kamar-Maheshwari algorithm, or (iv) Goldberg-Tarjan algorithm.

Dining problem Several families go out to dinner together. To increase their social interaction, they would like to sit at tables so that no two members of the same family are at the same table. Show how to find a seating arrangement that meets this objective (or prove that no such arrangement exists) by using a maximum-flow problem. Assume that the dinner contingent has p families and that the ith family has ai members. Also assume that q tables are available and the j th table has a seating capacity of bj . [Ahu93]

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail
Introduction to the Design and Analysis of Algorithms : Iterative Improvement : The Iterative Maximum-Flow Problem |

Related Topics