How to find a path in graph with maximum edges?

How does this algorithm to find the edges of the min cut of a graph work?

• http://stackoverflow.com/questions/4482986/how-can-i-find-the-minimum-cut-on-a-graph-using-a-maximum-flow-algorithm/21219223#21219223 The answer says that the min cut consists of the edges with reachable from vertex and unreachable to vertex. (reachability is from the source vertex) Also, do any other algorithms exist to find the min-cut?

• Answer:

  Thanks for the A2A. First set the weight of  the graph GGedges to 1,  use ford-fulkerson or edmond-karps algoirthm to compute the maximum flow. Both these algorithms work on adding flow along augmenting paths. So when you attain the maximum flow, there is surely no more augmenting path along which you can add more flow. Now do a dfs from the source to get all the vertices in the same cut as the source (say XX) and V(G)∖XV(G) \setminus X will give you the other part of the cut. The only problem with these algorithms are that these are slow, even edmond-karp algorithm has a runtime of O(VE2)O(VE^2). So a faster way to get a min cut is to use the following  randomized algorithm. Let GG be the graph on nn vertices and a mincut of size kk. 1. Pick an edge randomly (say (v1,v2)(v_1,v_2))and merge the two endpoints into a supervertex (say v12v_{12}). Merging involves removal of the edge  (v1,v2)(v_1,v_2), forming the supervertex v12v_{12}), adding the rest of the edges initially connected to either v1v_1 or v2v_2 to v12v_{12}. Continue this process untill you are left with only two vertices. Let the cut between them is of size k1k_1. Repeat the above procedure n22\frac{n^2}{2} times to get cuts of different sizes. Return the minimum of them as the mincut. With high probability this procedure returns a min cut. For the entire analysis, refer to Motwani-Raghwan textbook. http://dl.acm.org/citation.cfm?id=211390.