Given a network flow find if there's a min cut that only one of the given edges lay on it

Question

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.

Answer 1

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