0
$\begingroup$

while solving some questions about network flow I was wondering about the following statement:

Given a network flow (a graph $G=(V,E)$ with a source $s \in V$ and sink $t \neq s \in V$) > and an arbitrary vertex $v \in V$, how can we find if the vertex $v$ belongs to any minimum cut?

A vertex $v$ belongs to a minimum cut if it's reachable from the source in the residual graph induced by the flow.
My attempt first was: trying to find the maximum flow in the given network, then running BFS from the source on the residual graph in order to find the vertices in the minimum cut, if $v$ doesn't belong to the set of the vertices in the minimum cut that we have found then there is a minimum cut which $v$ is not part of it so we can return that the vertex $v$ doesn't belong to any minimum cut.
If $v$ belongs to the minimum cut then we have 2 options:

  1. All edges coming out of $v$ are saturated.
  2. There exists an edge coming out of $v$ which is not saturated.

For the first option we can try increasing the capacity of one of the edges coming out $v$ - run an augmenting path algorithm to see if the flow can be increased - if the flow has increased then we can conclude that the $v$ belongs to any minimum cut (otherwise, the flow would have stayed the same).
As for the second option, I have no idea what I can say about it, I'll appreciate any insights on how I can proceed further from here or to hear another approach. Thanks

Improve this question
$\endgroup$
5
  • $\begingroup$ When does a vertex belong to a minimum cut? $\endgroup$
    – Steven
    Feb 27 at 14:40
  • $\begingroup$ @Steven When the vertex is reachable from the source in the residual graph of the flow $\endgroup$
    – Yarin
    Feb 27 at 16:01
  • $\begingroup$ Are you interested in minimum or in minimal cuts? You write minimum in the body of your question but minimal in the title. $\endgroup$
    – Steven
    Feb 27 at 17:16
  • $\begingroup$ @Steven Supposed to be minimum cut, thank you for drawing my attention $\endgroup$
    – Yarin
    Feb 27 at 17:26
  • $\begingroup$ cs.stackexchange.com/q/42960/755, stackoverflow.com/q/29418244/781723, cs.stackexchange.com/q/117932/755 $\endgroup$
    – D.W. ♦
    Feb 27 at 17:27

0

Reset to default

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.