0
$\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$
  • 1
    $\begingroup$ What have you tried so far? $\endgroup$ – Anthony Labarre Jan 17 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 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 at 20:09
2
$\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$.

| cite | improve this answer | |
$\endgroup$

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.