HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Max-Flow: Detect if a given edge is found in some Min-Cut

Submitted by: @import:stackexchange-cs··
0
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.

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.

Context

StackExchange Computer Science Q#12507, answer score: 4

Revisions (0)

No revisions yet.