0
$\begingroup$

I was reading about max flow theorem and there I saw scenario where the min s-t cut is found. But wherever I searched they did it after knowing the max flow or by guessing the cuts by iterating almost all .

Is there a logical way to arrive at the minimum cut (with the paths) without knowing the maximum flow or guessing the cuts ?

Added thought: In a graph of say N vertices, and say one is source 's' and other is sink 't'. So there are 2^(N-2) possible s-t groupings. This is huge even for N = 8. So is iterating all the only way to get the answer. I was told that it is being asked in exams. Is it fair to ask such an itertative procedure in exam of limited time. How can one be sure that he has arrived at the correct answer without checking all (or without being given the max flow value)? For eg. finding the min cut as explained here .

enter image description here

$\endgroup$
7
  • $\begingroup$ Have you checked Wikipedia and other resources for algorithms for minimum s-t cut? $\endgroup$ Apr 2, 2017 at 6:59
  • $\begingroup$ yes. but all revolves around finding it given the max flow. $\endgroup$
    – learner
    Apr 2, 2017 at 7:09
  • $\begingroup$ The Wikipedia page mentions several algorithms that find the minimum cut directly. $\endgroup$ Apr 2, 2017 at 7:11
  • 1
    $\begingroup$ Closely related question -- duplicate? $\endgroup$
    – Raphael
    Apr 2, 2017 at 9:16
  • 2
    $\begingroup$ You need to elaborate why your titular question is not resolved by computing a max flow and deriving a min cut from that (iirc, no guessing has to be involved there). $\endgroup$
    – Raphael
    Apr 2, 2017 at 9:17

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.