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, 2019 at 23:03
  • 4
    $\begingroup$ Possible duplicate of Minimum-cut with minimum number of edges $\endgroup$ Sep 28, 2019 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, 2019 at 0:34
  • $\begingroup$ You can do it in various ways. I’ll let you work it out. $\endgroup$ Sep 29, 2019 at 7:01


Your Answer

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

Browse other questions tagged or ask your own question.