# Algorithm for seeing if there exists a min s-t cut (A,B) in a flow network with node u in A and node v in B

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.

• 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$.
– user114966
Mar 20 at 23:46
• @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.
– LTM
Mar 22 at 23:38

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