Skip to content

Maximum Flow

April 6, 2013

Imagine a directed graph with a source vertex (s), and a target/sink vertex (t), with each edge having a capacity. Capacity of edges can be thought of as size of a water pipe: the bigger the water pipe the larger the capacity. If you had a graph with these properties, then an s-t cut is defined as a partition between some set of vertices and the rest such that a sum of all the capacities of all the edges going out of the source side are counted, but NOT those entering the source side.

The minimum cut problem is to find the partitioning of vertices such that the s-t cut edge sum is the minimum of all possible s-t cuts. A historical example of the practicality of solving this problem can be found in the US Department of Defense recently declassified document here. The map shows how to completely cut-off flow of supplies from the USSR to Eastern Europe with the smallest cost, and therefore the minimum cut.

The maximum flow of an s-t directed graph, is to assign a flow to the overall graph such that the maximum units emanate from the source and terminate in the target.

The Max-flow min-cut theorem says that max-flow and min-cut are dual problems, and if you can solve Max-Flow, then you can easily also solve Min-Cut. For a max-flow solution to a graph, to obtain the min-cut of s-t, simply start at s and follow every forward edge not full, and every backward edge not empty using any graph searching algorithm (e.g. BFS, DFS).

A common algorithm to solve max-flow is Ford-Fulkerson’s algorithm. The algorithm is to start with each edge with an initial flow of zero. Then, while there exists and augmenting path: find that augmenting path, compute the bottleneck capacity, then increase the flow of that path by the bottleneck capacity. A variation of Ford-Fulkerson’s algorithm guaranteed to run in O(VE^2) time is Edmonds-Karp.

There are many application of Max-Flow, and research continues on this class of algorithm today. The search is on to either prove or disprove the possibility of a O(E) algorithm for max-flow. Some examples of max-flow applications are: bipartite matching, baseball elimination, and many more.

Advertisements

From → Algorithms

Leave a Comment

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

%d bloggers like this: