0
$\begingroup$

It's possible that by increasing an capacity in some edge that belongs to cross edge of an MIN-CUT, the max flow remain unchanged because there might be multiple min-cut. However, if I decrease the capacity; whether the MIN-CUT unique or not; it seems to me that the max flow will decrease the same amount. However, I can't prove that this holds for all cases (I mean not only integer capacity, but also non-integer, even irrationals)

$\endgroup$
0
$\begingroup$

Suppose $e$ is the edge whose capacity is reduced by $\delta$. The capacity of all cuts such that $e$ is one of their cross edges is decreased by $\delta$. The capacity of all other cuts is unchanged. If $e$ is a cross edge of a source-sink minimum cut, the capacity of the minimum cut decreases by $\delta$.

$\endgroup$
  • $\begingroup$ isn't that with irrational capacity, we can never have a min-cut? because the algorithm of finding max-flow will never halt $\endgroup$ – ElleryL Nov 8 '17 at 3:15
  • $\begingroup$ Some variants of the Ford-Fulkerson augmenting path method may not terminate on some networks with irrational capacities, but other variants are guaranteed to terminate. $\endgroup$ – Fabio Somenzi Nov 8 '17 at 4:05

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.