5

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.

  • 1
    I don't know the answer to your first question, but regarding your second: it's not quite fully specified, since e might appear in 2 different cuts, being minimum-weight in one but not the other. – j_random_hacker Jun 07 '13 at 13:29
  • 1
    Then i'll rephrase my question : is it possible to detect if it's the lightest weight in any minimum cut ? –  Jun 07 '13 at 13:33
  • You shouldn't [cross-post](http://cs.stackexchange.com/questions/12507/max-flow-detect-if-a-given-edge-is-found-in-some-min-cut). You should pick the most appropriate site and only post it there. – Bernhard Barker Jun 07 '13 at 16:42

1 Answers1

2

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.

Saeed Amiri
  • 22,252
  • 5
  • 45
  • 83
  • thanks for the answer , but what do you mean by " participating in at least one min-cut (that you already know it) " ? what I already know and how ? –  Jun 07 '13 at 15:55
  • @Itamar, If C-C'>=w(e), means e participating in some cut. But you know at least one of this cut, because is C'+e has this property. – Saeed Amiri Jun 07 '13 at 15:56
  • thanks again , I still got some questions - why C-C'>=w(e) and not C - C' > w(e) ? and how could I know from C-C'>=w(e) that e participate in some cut ? and is this cut minimal ? thanks again –  Jun 07 '13 at 15:59
  • suppose e is a bridge with minimum weight among all edges, then what happens? – Saeed Amiri Jun 07 '13 at 16:00
  • I'd really appriciate it if you could explain what do you mean –  Jun 07 '13 at 16:02
  • You know what is [bridge](http://en.wikipedia.org/wiki/Bridge_%28graph_theory%29)? If yes, then suppose your graph is unit weight and e is a bridge, so, e makes at least one min cut, then C-C' = w(e) = 1. – Saeed Amiri Jun 07 '13 at 16:04