1
$\begingroup$

I am confused from these 2 true-false questions on the max flow and am seeking clarity on the basics.

  • If in a network we increase the capacity of an edge in the minimum cut, the maximum flow gets increased.
  • If in a network we decrease the capacity of an edge in a minimum cut, the maximum flow gets decreased.

My thoughts:

  • Increase case: I think this is not always true as increasing the minimum could result in what was originally the $2^{nd}$ min flow becoming the lowest value and thus the new max flow. Hence because it isn't always true, the answer is false. This question indicates that max flow needs to be recalculated.

  • Decrease case: I think this is true because we already have the minimum cut so lowering the minimum brings us to a new minimum. Hence the answer is true.

Is my reasoning correct or is there something I misunderstood.

$\endgroup$
1
  • 1
    $\begingroup$ I think your reasoning is correct $\endgroup$
    – nir shahar
    Apr 20 at 16:14
1
$\begingroup$

Case 1, increase the weight. Consider a path on at least three vertices with capacity 1 for every edge. Max-flow is 1, min-cut is 1. Increase one of the edges' weight, and the max-flow will still be 1, hence the claim is false.

Case 2, let $C$ be a minimum cut with cost $w(C)$. Decrease the weight of one of the edges in $C$ to get a new minimum cost $w'(C)$. Since $C$ is still a cut in the graph, but $w'(C)$ is smaller than any other minimum cut, the claim is true.

$\endgroup$
2
  • $\begingroup$ If we applied Case 1 to a generic graph not just one with 3 vertices, could we then have a new max flow (min cut), that is, what used to be the 2nd largest max flow? $\endgroup$ Apr 20 at 20:18
  • 1
    $\begingroup$ Yes, create a path with edges with weight 1 and 2, and then you increase the weight from 1 to 3. $\endgroup$
    – Pål GD
    Apr 20 at 20:20

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.