Network Flow: Algorithm to find a cut of smallest capacity among all cuts

Question

You are given a flow network $G$ with $n > 4$ vertices. Besides the source $s$ and the sink $t$, you are also given two other special vertices $u$ and $v$ belonging to $G$. Describe an algorithm which finds a cut of the smallest possible capacity among all cuts in which vertex $u$ is at the same side of the cut as the source $s$ and vertex $v$ is at the same side as sink $t$.

Answer 1

Let's contract $s$ and $u$ into $s'$, $t$ and $v$ into $t'$ and let the resulting graph be $G'$.The problem you described is equivalent to the problem of finding a minimal $s'-t'$ cut in $G'$, which I'm sure you know how to solve.