patternMinor
Max-Flow: Detect if a given edge is found in some Min-Cut
Viewed 0 times
flowcutedgeminfoundmaxsomegivendetect
Problem
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.
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.
Solution
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.
Link to SO answer.
Context
StackExchange Computer Science Q#12507, answer score: 4
Revisions (0)
No revisions yet.