Given a Flow Network and an Edge e, Describe an Algorithm that Determines Whether e Crosses Some Minimum Cut

Question

Given a flow network G = (V,E) with a source s, a sink t and and edge e = (u,v), describe an algorithm that determines whether the edge e crosses some minimum cut (S,T).

My first idea was to calculate a maximum flow f and then decrease the capacity of e by some a > 0. Then we check if the residual graph has a path from s to t (it means that we can increase the flow f even more).

Now, if there is no path from s to t, we can be sure that e doesn't cross any minimum cut.

The problem is with the other direction. If there is a path from s to t, it might be because we have created a new minimum cut that e crosses by not being careful when choosing a > 0.

So how do I pick a small enough a > 0 ?

Answer 1

Its a cool question.

" My first idea was to calculate a maximum flow f and then decrease the capacity of e by some a... "

Did you mean increase? because the flow cant grow if you decrease the capacity..

Any way:

Run algo to find max flow and suppose flow is F.

Check if the flow flowing on e equals to its capacity,if not,then we return false.

Does it mean that if it is equals,e must cross some min cut?

Suppose e=(u,v):Because of the edges rule,the flow enters u must leave completely,

it means that for every cut you will take,will have some ecrooses it and e=(x,y),

we will have some path from u->v....->x or y->....u->v.

if we will delete this edge(e),and the flow will be decreased,it means that we cant,in any-way return the flow that came to x(or flow that left y cant find a way to the sink now) as it were before. it means e was in some min cut.

if the flow doesnt change,it only means that we found another way to return the flow that we "lost",so that means that e doesnt belong to any min cut because its not affects any Min cut capacity whitch equals to the max flow.

Your intuition to the problem is good,but see that it wont work because the increase/decrease of e can lead to no way,because there is a simple example where you change capacity of e and there is still no path from s to t in the residual network,but e still belong to some min cut.