# Maximum Flow

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.