1
$\begingroup$

Given a network flow $G=(V,E)$ with capacity function $C$ source $s$ and hole $t$, and given 2 edges $e_1 , e_2 $.

Find if there exists a min-cut such that only one of the edges belongs to the min-cut.

Hope to get help.

$\endgroup$
3
  • 1
    $\begingroup$ What have you tried so far? $\endgroup$ – Anthony Labarre Jan 17 '20 at 16:25
  • $\begingroup$ finding max flow, then I tried to prove that for example if both edges exist in the min-cut then it can't be that only one of them exists in another min-cut by assuming that there is such min-cut which means there is path to both vertices of one of the edges from s, but couldn't prove it, nor find contradiction... $\endgroup$ – omrib40 Jan 17 '20 at 16:28
  • $\begingroup$ Think I solved it - Compute max flow. if both satisfy f(e) = c(e) then , lets increment by one capacity to edge e1. again find max flow, if we found and it's bigger by 1 then e1 will lay on every min-cut,so that's useful information we can do also on e2. then just need to check if both lay on every min-cut then we done, if not we can decrement by one the edge that we don't know yet if she even lay on any cut, and again find flow, if it reduced by one then it lay on some cut since the other edge lay on any cut then we found solution. $\endgroup$ – omrib40 Jan 17 '20 at 20:09
3
$\begingroup$

First, compute the minimum cut value $c$ of the network.

Second, remove edge $e_1$ and increase the capacity of $e_2$ to infinity, then compute the minimum cut value $c_1$ of the new network.

Third, remove edge $e_2$ and increase the capacity of $e_1$ to infinity, then compute the minimum cut value $c_2$ of the new network.

Now you can check if $c-c_1\ge c(e_1)$ or $c-c_2\ge c(e_2)$ to see if there exists a min-cut in the initial network that contains exactly one of $e_1,e_2$.

$\endgroup$
5
  • $\begingroup$ Can you please elaborate why this is true? (maybe give an intuition, please) $\endgroup$ – Dennis Jan 5 at 9:11
  • 1
    $\begingroup$ @Dennis If $c-c_1\ge c(e_1)$, consider the min-cut in the new graph. The edge $e_2$ does not cross the cut because it has an infinite weight, so this cut has value $c(e_1)+c_1\le c$ in the original graph. Since $c$ is the minimum cut value in the original graph, this graph is also a min-cut in the original graph, and $e_1$ cross the cut while $e_2$ does not. $\endgroup$ – xskxzr Jan 6 at 1:32
  • 1
    $\begingroup$ On the other hand, if there is a min-cut in the original graph and only $e_1$ cross the cut, then this cut has value $c-c(e_1)$ in the new graph, which must be greater than the minimum cut value of the new graph, $c_1$. Hence, $c-c_1\ge c(e_1)$. $\endgroup$ – xskxzr Jan 6 at 1:35
  • $\begingroup$ Thank you, @xskxzr. Just to make sure: The reason we increase the capacity of $e_2$ to $\infty$ is to make sure it doesn't cross the min-cut in the new graph? $\endgroup$ – Dennis Jan 6 at 11:09
  • 1
    $\begingroup$ @Dennis You are right. $\endgroup$ – xskxzr Jan 7 at 1:38

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.