Given a network G=(V,E) , a max flow f and an edge e in E , I need to find an efficeint algorithm in order to detect whether there is some min cut which contains e. Another question is if I found out the e is contained in some min-cut, is it possible to detect whether it is the lightest edge across the cut?
I've thought about running Ford-Fulkerson algorithm, and the 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 greatful if anyone could point me to the solution , thanks in advance.
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'>=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.