My question is: in a DAG, each edge has a different value of capacity, we can assume these capacities are integers multiples of the total number of edges. Also, sometimes we can have many minimum cuts, but these cuts have a different number of edges, how can we know which cut has the maximal number of edges?

  • $\begingroup$ Remove $\epsilon$ from each weight, for small enough $\epsilon$. $\endgroup$ Sep 28 '19 at 23:03
  • 4
    $\begingroup$ Possible duplicate of Minimum-cut with minimum number of edges $\endgroup$ Sep 28 '19 at 23:04
  • $\begingroup$ @YuvalFilmus Thanks for the response, I have seen this link to find the minimum cut with the minimum number of edges. By removing small e, do you mean C * (|E| + 1) + 1 instead of + 1, I need to change it into C * (|E| + 1) - 1? $\endgroup$ Sep 29 '19 at 0:34
  • $\begingroup$ You can do it in various ways. I’ll let you work it out. $\endgroup$ Sep 29 '19 at 7:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.