Cut In a Flow Network

Question

Given $ N = (G = (V , E),s, t, c)$ a flow network (assume that the capacity $c$ is always positive) and $e = (u,v) \in E$.

I would like to develop an algorithm that tell if there exist a min-cut (cut with a minimum capacity)that the edge $e$ cross him.

I was thinking about running the Ford–Fulkerson algorithm to find the max flow and it is actually the capacity of the minimum cut according to Max-flow min-cut theorem and then I go over the Residual Network that was created and find the cut base on the nodes that can be reached from $s$ and then find if $e$ cross the cut or not.But it is only one minimum cut. there can be more minimum cut with the same capacity

Answer 1

Add the edges $su$ and $vt$ to the network with infinite capacity to obtain the modified network $N'$. It is not difficult to see that the finite ($st$-)cuts in $N'$ are precisely those finite cuts in $N$ that contain the edge $e$. This means that a min-cut in $N'$ is a min-cut in $N$ among those cuts that contain $e$. So you just have to check whether the min-cut in $N'$ has the same capacity as the min-cut in $N$, which can be done using the Ford-Fulkerson (or, to be more precise, the Edmonds-Karp) algorithm.

Note that this method easily generalizes to the case when you have multiple prescribed edges.