Given a weighted directed graph, we want to find the globally minimal cut - that is, a set of edges that if removed separate the graph in two halves and that have the minimal amount of total weight compared to any other such cut.
Now, although the following seems to work, I've been told that the reasoning is wrong. But quite frankly, I don't see how and I'm not sure about how certain he was:
Consider the sets of nodes U,V that are separated by the globally minimal cut (i.e. the s-t-cut, where s in U, t in V). Note: we don't care about the edges back from V to U.
For any u in U, v in Vm the u-v-cut cannot be smaller than the s-t-cut, otherwise, the s-t-cut would not be (globally) minimal. For the same reason, no cut between two vertices in u or two vertices in V can be smaller.
On the other hand, the u-v-cut cannot be greater either, otherwise, it would need to include some edges U->V not part of the s-t-cut, which means the s-t-cut is no cut at all.
It is sufficient, therefore, to fix s arbitrarily and iterate over all other vertices x. s is either in U, then the s-x-cut corresponds to the global minimum if x is in V, or the x-s-cut does if s is in V and x is in U. If they are both part of the same set, the cut will be at least as great (but possibly greater) as the global minimum.
Therefore, we will eventually find the global minimum by calculating both, and keeping track of the minimum cut encountered so far.
It seemed to make sense to me. Am I wrong? And if so, why?
My interpretation is that you're basically asking the following question:
Can we find a global minimum cut by fixing an arbitrary vertex s and computing all s-t and t-s min cuts for all vertices t != s?
The answer is yes, and it's easy to prove: Consider a global min-cut (U, V) with value C. Then either s is in U or s is in V.
Case 1: s is in U. By definition of a minimum cut we have V != {}, so there is a vertex t in V. Then (U, V) is a valid s-t cut, so the minimum s-t cut will have value at most C
Case 2: s is in V. Then there exists a vertex t in U and the same argument as above holds for the minimum t-s cut
This algorithm is described for example in Chapter 6.4 of these MIT lecture notes.