0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Welcome to Stackexchange. You'll find that simple "Here's the statement of my question, solve it for me" posts will be poorly received. What is better is for you to add context (with an edit): What you understand about the problem, what you've tried so far, etc.; something both to show you are part of the learning experience and to help us guide you to the appropriate help. You can consult this link for further guidance $\endgroup$ – Brian Apr 9 at 10:10
  • $\begingroup$ Let me know when you find a solution! $\endgroup$ – mathpadawan Apr 10 at 2:24
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

I'm sorry but I have to tell I don't know how to contract $s$ and $u$.Could you tell more details?

$\endgroup$
  • $\begingroup$ Welcome to MSE. This should be a comment, not an answer. $\endgroup$ – José Carlos Santos Apr 13 at 8:52

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.