3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

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.