1
$\begingroup$

The max-flow min-cut theorem guarantees that the min-cut of a directed network equals the maximum flow. And we can compute $S$ and $T$, are disjoint subsets containing source node and sink node respectively from the residual graph.

What will be $S$ and $T$ if the max-flow from source to sink is 0, that is, there is no directed path from $s$ to $t$? Is $S$ going to be the singleton set {s} or its the empty set $\phi$ and $T$ be the vertex set $V$?

$\endgroup$
  • $\begingroup$ Have you checked the relevant definitions? Have you constructed a few simple examples? $\endgroup$ – Apass.Jack Mar 13 at 2:55
  • $\begingroup$ @Apass.Jack, my gut feeling is, if the flow from source to sink is zero, then $S$ should be the singleton $S$ and $T$ should be the other vertices of the graph, but I can't seem to find anything in the literature to support this. All discussions assume there is some non-zero flow from source to sink. I want to use the min-cut as a subroutine in another algorithm and this result will greatly affect the outcome of the algorithm. $\endgroup$ – Ozymandais Mar 13 at 3:12
2
$\begingroup$

No, your gut feeling is not correct.

Consider the following flow network with source $s$ and sink $t$, where the capacity of every edge is 1. The max-flow from source to sink is 0. The s-t cut $(\{s,A\}, \{B,t\})$ is a minimum cut since the only connecting edge $(B, A)$ goes from sink side to source side.

$$ s \longrightarrow A \longleftarrow B \longrightarrow t$$

You could learn several lessons from this simple problem. One is that source and sink are symmetric in some strong sense. It looks like your gut feeling does not respect this symmetry. Another lesson is that a few simple examples should be included in your repository. Always try constructing some simple or extreme examples when you want to check a proposition of unknown truth value.

$\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.