find the union of all min cuts of a flow network

Question

I'm trying to solve the following question :

Given a flow network $N = (G=(V,E),c,s,t)$. Let $\mathcal F$ be the set of all minimum cuts. Prove that $\mathcal F$ is closed under intersections and unions, i.e. for every $ S_1,S_2\in\mathcal F , S_1 \cup S_2 \in \mathcal F$ and $ S_1 \cap S_2 \in \mathcal F $.

that part I took care of just fine using the min-cut-max-flow theorem.

the other part is the one that I had trouble with :

Given a max flow $ f $,find $S_{\min} = \bigcap_{S\in\mathcal F} S \text{ and } S_{\max} = \bigcup_{S\in\mathcal F } S $.

I realized that when considering a min cut $(S,T)$ , and given the residual graph (which can be built from the given maximum flow) , every vertex that's reachable from $s$ (source node) , must be in $S$ , so I was able to use that to come up with an algorithm to find $S_{\min}$.

But as for finding an algorithm for $S_{\max}$, I'm kinda having trouble putting my finger on a property of a min cut edge, i.e. what does it take to be a cut edge (or for a vertex to be in $S$) of some min cut?

I'm not looking for the full answer but rather a hint.. any help is appreciated.

Answer 1

Note $S_{\max}=V-\bigcap_{S\in\mathcal{F}}(V-S)$. And $\bigcap_{S\in\mathcal{F}}(V-S)$ is the set of all vertices from which $t$ is reachable in the residual graph.

The reason why $\bigcap_{S\in\mathcal{F}}(V-S)$ is the set of all vertices from which $t$ is reachable in the residual graph is the same as the reason why $S_{\min}$ is the set of all vertices that are reachable from $s$. You can prove this using the complementary slackness conditions.