Let $G\langle V,E\rangle$, a flow-network. I need to check if there's an edge such that increasing it's capacity would increase the max flow of the graph.
There's such an edge, if there's a path, $p$, from $s$ to $t$ such that there's exactly one saturated edge in $p$.
So the problem is reduced to checking if such a path exists.
I think I could utilize BFS algorithm for that cause. Basically I could tag each scanned vertex "If we reached it by a path contains a saturated edge" and each vertex could get into queue more than one time.
I'm having troubles with formalizing it into a proof.
Is that a good approach? Can you help me with proving/formalizing it?
Thanks.