Question

6. Suppose that you are trying to find a max flow in a directed graph. However, instead of having capacities on the edges, you have capacities on the nodes. In other words, each node can only accept a certain amount of total incoming flow. (Can you think of a real-life application for this kind of problem?) Show how to find a max flow in such a case. Hint: think about how to modify the graph, rather than the algorithm.

Treat single arithmetic operations (addition, subtraction, multiplication, and division) as constant time operations.

Answer 1

In the first section we remind some necessary definitions and statements of the maximum flow theory. Other sections discuss the augmenting path algorithms themselves. The last section shows results of a practical analysis and highlights the best in practice algorithm. Also we give a simple implementation of one of the algorithms.

Statement of the Problem
Suppose we have a directed network G = (V, E) defined by a set V of nodes (or vertexes) and a set E of arcs (or edges). Each arc (i,j) in E has an associated nonnegative capacity u_ij. Also we distinguish two special nodes in G: a source node s and a sink node t. For each i in V we denote by E(i) all the arcs emanating from node i. Let U = max u_ij by (i,j) in E. Let us also denote the number of vertexes by n and the number of edges by m.

We wish to find the maximum flow from the source node s to the sink node t that satisfies the arc capacities and mass balance constraints at all nodes. Representing the flow on arc (i,j) in E by x_ij we can obtain the optimization model for the maximum flow problem:

Maximize f(x)= Σ zij subject to (j)EE uij 0€ zij V (i.jje E

Vector (x_ij) which satisfies all constraints is called a feasible solution or, a flow (it is not necessary maximal). Given a flow x we are able to construct the residual network with respect to this flow according to the following intuitive idea. Suppose that an edge (i,j) in E carries x_ij units of flow. We define the residual capacity of the edge (i,j) as r_ij = u_ij – x_ij. This means that we can send an additional r_ij units of flow from vertex i to vertex j. We can also cancel the existing flow x_ij on the arc if we send up x_ij units of flow from j to i over the arc (i,j).

So, given a feasible flow x we define the residual network with respect to the flow x as follows. Suppose we have a network G = (V, E). A feasible solution xengenders a new (residual) network, which we define by G_x = (V, E_x), where E_x is a set of residual edges corresponding to the feasible solution x.

What is E_x? We replace each arc (i,j) in E by two arcs (i,j), (j,i): the arc (i,j) has (residual) capacity r_ij = u_ij – x_ij, and the arc (j,i) has (residual) capacity r_ji=x_ij. Then we construct the set E_x from the new edges with a positive residual capacity.

Augmenting Path Algorithms as a whole
In this section we describe one method on which all augmenting path algorithms are being based. This method was developed by Ford and Fulkerson in 1956 [3]. We start with some important definitions.

Augmenting path is a directed path from a source node s to a sink node t in the residual network. The residual capacity of an augmenting path is the minimum residual capacity of any arc in the path. Obviously, we can send additional flow from the source to the sink along an augmenting path.

All augmenting path algorithms are being constructed on the following basic idea known as augmenting path theorem:

Theorem 1 (Augmenting Path Theorem). A flow x* is a maximum flow if and only if the residual network Gx* contains no augmenting path.

According to the theorem we obtain a method of finding a maximal flow. The method proceeds by identifying augmenting paths and augmenting flows on these paths until the network contains no such path. All algorithms that we wish to discuss differ only in the way of finding augmenting paths.

We consider the maximum flow problem subject to the following assumptions.

Assumption 1. The network is directed.

Assumption 2. All capacities are nonnegative integers.

This assumption is not necessary for some algorithms, but the algorithms whose complexity bounds involve Uassume the integrality of the data.

Assumption 3. The problem has a bounded optimal solution.

This assumption in particular means that there are no uncapacitated paths from the source to the sink.

Assumption 4. The network does not contain parallel arcs.

This assumption imposes no loss of generality, because one can summarize capacities of all parallel arcs.

As to why these assumptions are correct we leave the proof to the reader.

It is easy to determine that the method described above works correctly. Under assumption 2, on each augmenting step we increase the flow value by at least one unit. We (usually) start with zero flow. The maximum flow value is bounded from above, according to assumption 3. This reasoning implies the finiteness of the method.

With those preparations behind us, we are ready to begin discussing the algorithms.