4
$\begingroup$

Given a network $G=(V,E)$ , a max flow f and an edge $e \in E$ , I need to find an efficient algorithm in order to detect whether there is some min cut which contains $e$. Another question is, how do I decide whether if $e$ is the lightest edge of at least one minimal cut?

I've thought about running Ford-Fulkerson algorithm, and then increasing / decreasing the capacity of the given edge and see what happens, but I haven't came up with something that might help me solve the problem.

I'd be grateful if anyone could point me to the solution, thanks in advance.

$\endgroup$
3
$\begingroup$

Here is a solution for the first question: Suppose $w(e)$ is the weight of $e$, calculate min-cut value for $G$, suppose is $C$. Then we remove $e$ from $G$ to make $G'$; again we calculate the min-cut value for $G'$, suppose is $C'$, if $C-C'\ge w(e)$, then this concludes that $e$, participating in at least one min-cut (that you already know it), otherwise $e$ does not belong to any min-cut.

Link to SO answer.

$\endgroup$
2
$\begingroup$

If you only have rational capacities, multiply¹ them to become integral and then decrease the capacity of $e$ by e.g. $0.5$¹. Then every two cuts differ only by integers (before you decrease) and a cut that contains $e$ can't get minimal if it wasn't before. On the other hand a minimal cut that contains $e$ has now strictly smaller capacity than before and thus it has a smaller capacity than all cuts that do not contain $e$ (they weren't decreased).

Now you compute a maximal flow and if its value decreased, any minimal cut (like the one that separates vertices reachable from the source in the residual network from the rest) contains $e$, if it didn't decrease, $e$ is not contained in any minimal cut.

¹ If you don't like the multiplication, you can also compute the smallest common denominator $d$ of all weights and use $\frac{d}{2}$ instead of $0.5$.

$\endgroup$
  • $\begingroup$ Thanks for the answer, but there are still some issues that are not clear enough : 1 - I aim to find out whether e is contained in some minimal cut , not in every minimal cut 2 - I don't want to find the lightest edge , I'd like to find out if e is the lightest edge in some minimal cut $\endgroup$ – itamar Jun 7 '13 at 14:28
  • $\begingroup$ i don't know if e is in some minimal cut , I want to find out whether it's found in a minimal cut or not $\endgroup$ – itamar Jun 7 '13 at 14:43
  • $\begingroup$ @Itamar: I edited your question and my answer, according to the comments on Stack Overflow, so please remove (and reformulate) your comments here to. $\endgroup$ – frafl Jun 7 '13 at 20:53

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.