I am struggling with the following question (and solution actually):
Given $G(V,E)$, a flow-network (capacities are integers), We denote the maximum-flow value by $f^*$. Check for an edge $e$ if:
1. It crosses some minimal-cut.
2. It crosses every minimal-cut.
The solution suggests:
- Decrease the capacity of the edge $e$ by $1$ and check if the new maximum flow equals $f^*-1$. return true if so.
- Increase the capacity of the edge $e$ by $1$ and return true iff the max-flow increased.
I'd be glad if you could explain to me what's the idea behind this algorithm.
Thanks
The idea is to use the max flow-min cut theorem on several levels.
For 1., suppose $e$ is in some minimal cut $C$. Then $f^*=u(C)$ where $u$ is the capacity vector. Now, if we decrease the capacity of $e$ by 1, we get $\tilde{u}(C)=u(C)-1=f^*-1$, where $\tilde{u}$ is the new capacity vector. But $C$ is still a minimal cut with respect to $\tilde{u}$ (do you see why?), so by the max flow-min cut theorem the new optimal flow is $f^*-1$ and the algorithm returns true.
On the other hand, if the algorithm returns true, then by a similar argument you get that since the new optimal flow is $f^*-1$, the minimal cut value has decreased by 1. And that can only happen if $e$ is in some minimal cut.
The second question is (very) similar, I let you try it.