Find all edges in min-cut

Question

Let (G,s,t,{c}) be a flow network, and let F be the set of all edges e for which there exists at least one minimum cut (A,B) such that e goes from A to B. Give a polynomial time algorithm that finds all edges in F.

NOTE: So far I know I need to run Ford-Fulkerson so each edges has a flow. Furthermore I know for all edges in F, the flow f(e) = c(e). However not all edges in a graph G which respects that constraint will be in a min-cut. I am stuck here.

Answer 1

Suppose you have computed a max flow on a graph G and you know the flow through every edge in the graph. From the source vertex s, perform a Breadth First Search OR Depth First Search on the original graph and only traverse those edges that have flow less than the capacity of the edge. Denote the set of vertices reachable in this traversal as S, and unreachable vertices as T.

To obtain the minimum cut C, we simply find all edges in the original graph G which begin at some vertex in S and end at some vertex in T.

This tutorial in Topcoder provides an explanation / proof of the above algorithm. Look at the section beginning with the following text:

A cut in a flow network is simply a partition of the vertices in two sets, let's call them A and B, in such a way that the source vertex is in A and the sink is in B.

I shall attempt to provide an explanation of the corresponding section in the Topcoder tutorial (just for me to brush up on this as well).

Now, suppose that we have computed a max flow on a graph G, and that we have computed the set of edges C using the procedure outlined above. From here, we can conclude several facts.

Fact 1: Source vertex s must be in set S, and sink vertex t must be in set T.

Otherwise, vertices s and t must be in the same set, which means that we must have found a path from s to t consisting only of edges that have flow less than capacity. This means that we can push more flow from s to t, and therefore we have found an augmenting path! However, this is a contradiction, since we have already computed a max flow on the graph. Hence, it is impossible for source vertex s and sink vertex t to be connected, and they must be in different sets.

Fact 2: Every edge beginning at set S and ending at set T must have flow == capacity

Again we prove this by contradiction. Suppose that there is a vertex u in S and a vertex v in T, such that edge (u,v) in the residual network has flow less than capacity. By our algorithm above, this edge will be traversed, and vertex v should be in set S. This is a contradiction. Therefore, such an edge must have flow == capacity.

Fact 3: Removing the edges in C from graph G will mean that there is no path from any vertex in set S to any vertex in set T

Suppose that this is not the case, and there is some edge (u,v) that connects vertex u in set S to vertex v in set T. We can separate this into 2 cases:

1. Flow through edge (u,v) is less than its capacity. But we know this will cause vertex v to be part of set S, so this case is impossible.
2. Flow through edge (u,v) is equal to its capacity. This is impossible since edge (u,v) will be considered as part of the edge set C.

Hence both cases are impossible, and we see that removing the edges in C from the original graph G will indeed result in a situation where there is no path from S to T.

Fact 4: Every edge in the original graph G that begins at vertex set T but ends at vertex set S must have a flow of 0

The explanation on the Topcoder tutorial may not be obvious on first reading and the following is an educated guess on my part and may be incorrect.

Suppose that there exists some edge (x,y) (where x belongs to vertex set T and y belongs to vertex set S), such that the flow through (x,y) is greater than 0. For convenience, we denote the flow through (x,y) as f. This means that on the residual network, there must exist a backward edge (y,x) with capacity f and flow 0. Since vertex y is part of set S, the backward edge (y,x) has flow 0 with capacity f > 0, our algorithm will traverse the edge (y,x) and place vertex x as part of vertex set S. However, we know that vertex x is part of vertex set T, and hence this is a contradiction. As such, all edges from T to S must have a flow of 0.

With these 4 facts, along with the Max-flow min-cut theorem, we can conclude that:

1. The max flow must be less than or equal to the capacity of any cut. By Fact 3, C is a cut of the graph, so the max flow must be less than or equal to the capacity of cut C.

2. Fact 4 allows us to conclude that there is no "back flow" from T to S. This along with Fact 2 means that the flow consists entirely of "forward flow" from S to T. In particular, all the forward flow must result from the cut C. This flow value happens to be the max flow. As such, by the Max-flow min-cut theorem, we know that C must be a minimum cut.