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

$\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
    Mar 20 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
    Mar 22 at 23:38
0
$\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]$.

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