3

Given a network N, I want to find the minimum cut that has the lowest number of edges in it. I thought about:

Find the maximum flow (with Dinitz algorithm for example)
Increase the capacity function such that for every edge e c'(e)=c(e)+1, then use Dinitz algorithm again and calculate the difference.
That difference will be the minimum number of edges in the mincut.

But I got stuck proving it.

Is the concept wrong? Or am I just proving it wrong?

General Grievance
  • 4,555
  • 31
  • 31
  • 45
Yinon Eliraz
  • 317
  • 1
  • 6
  • 22

1 Answers1

0

You cannot make the new capacity of edge c'(e)=c(e)+1, this is a wrong prove, because the min cut may change after this transformation. You can make the capacity of new graph c'(e)=c(e)*(|E|+1)+1, in which (|E|+1) should be big enough.

Qianyang Peng
  • 1