2
$\begingroup$

We are given a flow network and two nodes $u$ and $v$. We want to create an algorithm that tells us whether or not there is a minimum s-t cut so that $u$ belongs to the same side of the cut as the source node $s$ and $v$ belongs to the same side of the cut as the sink node $t$.

My initial idea was to run Ford-Fulkerson to get the residual graph $G_f$ at the end. Then use that to find all nodes reachable from $s$ in $G_f$ (call this set $A$) then $B=V-A$ where $V$ is the vertex set. Then $(A,B)$ is a min s-t cut and if $u \in A, v \in B$ output true, else false.

But since there may be more than one min cut I'm a bit stuck.

Improve this question
$\endgroup$
2
  • $\begingroup$ I'm not fully confident, but the following should work. Essentially, you need to find a min-cut between sets $\{s,u\}$ and $\{t,v\}$. For this, find a max flow with sources $s$ and $u$ and sinks $t$ and $v$. After that, check that the value of this flow matches the value of the min cut between $s$ and $t$. $\endgroup$
    – user114966
    Commented Mar 20, 2021 at 23:46
  • $\begingroup$ @Dmitry $u$ could have incoming edges and $t$ could have outgoing edges. I'm not sure how to run Ford-Fulkerson on something like that. $\endgroup$
    – LTM
    Commented Mar 22, 2021 at 23:38

1 Answer 1

Reset to default
1
$\begingroup$

The easy solution is to add an edge between $s$ and $u$ with infinite weight and $t$ and $v$ with infinite weight.

Note though that this doesn't mean that $s$ and $u$ will be connected in $G[A]$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I agree that if the max-flow of the new graph changes then the vertices were part of every cut. But, if the max-flow of the new graph stays the same, nodes u,v could've been part of a min-cut ( in such a case, there were at-least two min-cuts ), but not necessarily so; how do we verify this? $\endgroup$
    – flamel12
    Commented Jul 9, 2023 at 13:24
  • $\begingroup$ OP asks for a minimum cut. $\endgroup$
    – John K.
    Commented Jul 10, 2023 at 11:19
  • $\begingroup$ For some vertices $u,v$ we want to find if there exists a min-cut $(S,T) $ s.t. $ u \in S $ and $ v \in T $. Why running FF method on the new graph you proposed does satsify those vertices membership in $(S,T)$? ( I don't understand the correctness of your algorithm ) $\endgroup$
    – flamel12
    Commented Jul 10, 2023 at 11:52
  • $\begingroup$ Any edge across a cut is at capacity in the residual graph. If a minimum cut does not contain neither $su$ nor $vt$, then the cut will remain at capacity. $\endgroup$
    – John K.
    Commented Jul 10, 2023 at 12:09

Your Answer

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

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