2
$\begingroup$

After applying an algorithm (like Ford-Fulkerson) that gives you the max flow over a graph $G(V,E)$, how do you determine the actual edges that belong to the minimal cut (recall the Max Flow/ Min Cut theorem)?

I know that the set of edges might not be unique, but what I want is to determine one set of edges (of the possible solutions) that will give me the minimal cut.

In problems like image segmentation, determining the actual edges that form the cut is necessary to determine to which segment a certain pixel belongs to.

Finding the saturated edges isn't enough: there might be saturated edges that do not belong to the cut. (https://stackoverflow.com/questions/4482986/how-can-i-find-the-minimum-cut-on-a-graph-using-a-maximum-flow-algorithm)

$\endgroup$
2
$\begingroup$

Let $s$ and $t$ denote the source and the sink of your network.

Remove all saturated edges from the graph $G$. Then $s$ and $t$ will be disconnected (otherwise you could find an augmenting path).

Now it is easy to show that the edges leaving the connected component containing $s$ will form a min cut. The connected component can be found in linear time by using BFS.

$\endgroup$
  • $\begingroup$ I am sorry, but I don't get it. What do you mean by " the connected component containing s will form a min cut"? Shouldn't the min cut be a subset of the saturated edges and not of the connected component containing either s or t? $\endgroup$ – Vasco Mota Feb 21 '14 at 17:31
  • $\begingroup$ @VascoMota I updated the answer to be more clear: The edges leaving the connected component (which will be only saturated edges you removed from $G$ initially) will form a min cut. $\endgroup$ – Listing Feb 21 '14 at 17:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.