# 6.4   Maximum Flow

This section under major construction.

## Maximum flow and minimum s-t cut.

Program FordFulkerson.java computes the maximum flow and minimum s-t cut in an edge-weighted digraph in E^2 V time using the Edmonds-Karp shortest augment path heuristic (though, in practice, it usually runs substantially faster). It uses FlowNetwork.java and FlowEdge.java.

## Percolation.

Max flow in 2D (always choose leftmost path) and 3D.

## Applications to computer graphics.

Yuri Boykov has papers on maxflow applications to segmentation in computer vision. maxflow data.

## Bipartite matching.

#### Exercises

1. Cycle containing two vertices. Given an undirected graph G and two distinguished vertices s and t, find a cycle (not necessarily simple) containing s and t, or report that no such cycle exists. Your algorithm should run in linear time.

Answer. The answer is yes if and only if the maximum flow from s to t is at least 2. So, run two iterations of Ford-Fulkerson in the digraph with each edge replace by two antiparallel edges and unit capacity.

2. k-connected. Given an undirected graph, determine whether two vertices s and t are k-connected (or equivalently whether there are k edge-disjoint paths).
3. True or false. If true provide a short proof, if false give a counterexample.
• In any max flow, there is no directed cycle on which every edge carries positive flow.
• There exists a max flow for which there is no directed cycle on which every edge carries positive flow.
• If all edge capacities are distinct, the max flow is unique.
• If all edge capacities are distinct, the min cut is unique.
• If all edge capacities are increased by an additive constant, the min cut remains unchanged.
• If all edge capacities are multiplied by a positive integer, the min cut remains unchanged.
4. Simple cycle containing two vertices. Given an undirected graph and two vertices s and t, find a simple cycle containing both s and t (or report that no such cycle exists).

Hint: there is a directed cycle containing both s and t if and only if there are two (internally) vertex-disjoint paths between s and t.

5. Vertex disjoint paths in an digraphs. Given a digraph G and two vertices s and t, find the maximum number of of vertex-disjoint paths from s and t.

Hint: Replace each vertex v (other than s and t) with two vertices v1 and v2; add an edge of capacity 1 from v1 to v2; redirect all edges pointing to v to point to v1; redirect all edges pointing from v to point from v2.

6. Vertex disjoint paths in an undirected graph. Given an undirected graph G and two vertices s and t, find the maximum number of of vertex-disjoint paths between s and t.

Hint: Replace each undirected edge v-w by two directed edges v->w and w->v.

7. Simple path containing three vertices. Given an undirected graph and three vertices u, v, and w, find a simple path containing both u, v, and w (or report that no such path exists).

Hint: there is a simple path between u and w that passes through v if and only if there are two (internally) vertex disjoint paths, one between v to u and one between v to w.

8. Unique mincut. Given an s-t flow network, determine whether the mincut is unique.

Hint: solve s-t mincut problem in G and in G^R.

9. Unmatchable edges in a bipartite graph. Given a bipartite graph G, an edge is unmatchable if it does not appear in any perfect matching of G.

Hint: if G has no perfect matching, then all edges are unmatchable. Otherwise, find a perfect matching; orient all of the edges in the perfect matching in one direction and all of the remaining edges in the opposite direction; the unmatchable edges are all of the edges not in the perfect matching that have endpoints in different strongly-connected components of the resulting digraph.

10. Mincut with fewest edges. Given a flow network, among all mincuts, find one that has the fewest number of edges.

Hint: create a new flow network G' that is equal to G, except that w'(e) = w(e) * n + 1.