# 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, 2021 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, 2021 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]$$.
• 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 ) Jul 10 at 11:52
• 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. Jul 10 at 12:09