1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.