The Maximum Flow Problem

A flow network is a directed graph where each edge has a nonnegative capacity and two vertices are distinguished as a source and a sink. A flow in a flow network is a function that maps edges to real numbers and satisfies two requirements:

(1) For each edge, the flow through the edge is equal to or less than the capacity of the edge.

(2) For each vertex other than the source and the sink, the amount of flow going into the vertex is equal to the amount of flow going out of it. The requirement does not apply to the source because the source does not have any flow going into it, and the requirement does not apply to the sink because the sink does not have any flow going out of it.

The value of a flow is the total amount of flow going into the sink. A maximum flow is a flow of maximum value. The maximum flow problem is to find a maximum flow, given a flow network.

For any two vertices u and v, if (u, v) is an edge in the flow network, then the residual capacity of u and v is the difference between the capacity of (u, v) and the flow through (u, v). If instead (v, u) is an edge in the flow network, then the residual capacity of u and v is the flow through (v, u). If neither (u, v) nor (v, u) is an edge in the flow network, then the residual capacity of u and v is zero.

A residual network is another directed graph. It has all of the vertices that the flow network has, but it includes an edge (u, v) if and only if the residual capacity of u and v is positive.

An augmenting path is a path from the source to the sink in the residual network. A flow in a flow network is maximum if and only if the corresponding residual network has no augmenting path. This fact yields a useful method. The Ford-Fulkerson method starts with an initial flow, and, while there is an augmenting path, it uses the augmenting path to increase the total flow.

The Edmonds-Karp algorithm is an instance of the Ford-Fulkerson method that uses breadth-first search to look for augmenting paths. The Edmonds-Karp algorithm runs in O(V * E^2) time.

Many linear programming problems can be modeled as network-flow problems, and network-flow algorithms can solve these problems much faster than general-purpose linear programming methods. I implemented Edmonds-Karp in Java to solve an instance of the maximum bipartite matching problem.

My Java implementation of Edmonds-Karp is up at my GitHub.

References:

Cormen, Thomas, Charles Leiserson, Ronald Rivest, and Clifford Stein. Introduction to Algorithms (3rd ed.). Cambridge, MA: The MIT Press, 2009.

Ford, L. R., and D. R. Fulkerson. Flows in Networks. Princeton, NJ: Princeton University Press, 1962.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s