I want S to be as big as possible in a min-cut in a flow network.
I have found the following idea:
Could I change the algorithm there a bit, after running EK to flip all vectors, run BFS from t, and all the nodes you can reach from t are in T for all min-cuts of the flow network? (and there for-all these nodes are the minimum group for T, and it answers....)
Thank you!!
Edit: Here is my prof: From a minimal ST cross-section: every vector that crosses the cross section from S to T is saturated, therefore all vectors that cross from S to T have a residual capacitance of 0 in the last residual graph. Therefore, when we reversed the directions of the vectors, we get: every vector that crosses a minimal cross section has a residual capacitance of 0 in the direction from T to S. Now - any vector that is not 0 in the direction of T to S cannot cross a minimal cross-section. That's why in the graph we built - every path of vectors with a positive capacity that starts from t which is in T, must stay in T. We got the minimal cut that makes T the smallest possible group among the min- cuts - all those that really have to be in T, those who don't have to - won't be.