1
$\begingroup$

Let $G$ be a flow network, where $c(e)$ is the capacity of an edge, and the source is $s$ and sink $t$. Define a node $v$ to be "source-like" if for every min-cut $(S,T)$ of $G$ where $S$ contains $s$, $S$ contains $v$. Find an efficient algorithm to determine the source-like nodes.

I was thinking that since Ford-Fulkerson is efficient, we can go ahead and run that to get the max flow solution, and perhaps use that to find the source-like nodes. However, as I look at examples and try to think of what to do with the flow network, I don't see how to identify source-like nodes.

Of course when you look at the residual graph at the end of Ford-Fulkerson, there is a cut where all the edges point away from $t$ and toward $s$ roughly speaking. This cut is a min-cut. But it is just one min-cut. I'm not sure how to work in the idea of all possible min-cuts. Cutting an edge seems like a bad idea. Redirecting flow in small changes seems like a bad idea.

When I think of a graph where I can trivially spot two distinct min-cuts, I think of:

s -> b weight 3
s -> c weight 3
b -> d weight 3
c -> e weight 3 
d -> t weight 3
e -> t weight 3

Basically this just sets up two parallel tracks. In fact as I think about it, here I think the source-like node would be the source node.

I wonder if it's the case that in any max-flow solution, every min-cut is some set of edges which are completely used up by the max-flow?

$\endgroup$
1
  • $\begingroup$ Was my answer helpful? Have you considered upvoting and accepting my answer? Please comment if my answer can be improved. (This comment will be deleted upon feedback.) $\endgroup$
    – John L.
    Jun 30, 2022 at 13:35

1 Answer 1

1
$\begingroup$

The example given in the question suggests that we want to find the min-cut that is "nearest" to the source $s$.

The answer is "the first" min-cut yielded by a max-flow. More specifically, find a max-flow $f$ of $G$, which can be done efficiently by Ford-Fulkerson algorithm or other algorithms. Let $G_f$ be the residual network of $f$. Let $S$ be the set of the nodes reachable from $s$ in $G_f$. Then $S$ is the set of all source-like nodes.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.