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.
$\begingroup$
$\endgroup$
3
-
1$\begingroup$ What have you tried so far? $\endgroup$– Anthony LabarreCommented Jan 17, 2020 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$– BOB123Commented Jan 17, 2020 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$– BOB123Commented Jan 17, 2020 at 20:09
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
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$.
-
$\begingroup$ Can you please elaborate why this is true? (maybe give an intuition, please) $\endgroup$– DennisCommented Jan 5, 2021 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$– xskxzrCommented Jan 6, 2021 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$– xskxzrCommented Jan 6, 2021 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$– DennisCommented Jan 6, 2021 at 11:09
-
1