9
$\begingroup$

I have been asked the following question:

Let G be an input graph to the max flow problem. Let (A, B) be a minimum capacity s−t cut in the graph. Suppose we add 1 to the capacity of every edge in the graph. Is it necessarily true that A is still a minimum cut?

My initial intuition says that it would not change. The reasoning is because we know that the minimum s-t cuts capacity is equal to the max-flow in the graph. So, if we were to change all the values by adding 1 and calculated the max-flow we would get the same answer plus some constant since all the edges are still going to be considered in the same order since there order is still conserved. Thus, we would have the same cut.

I am having trouble formulating my ideas precisely so any advice or hints would be great. I have been trying to come up with a counter example, but since it must be all integers I am having a hard time. Thanks!

$\endgroup$

2 Answers 2

Reset to default
6
$\begingroup$

This is not the case. consider this(poorly drawn) counter example:enter image description here

let all the edges be directed from left to right. Let s, the source be the left-most vertex and t, the sink be the right-most. Then the minimum cut separates t from everything else, but adding one to the capacity of each arc changes the minimum cut to be the one that separates s from everything else.

$\endgroup$
4
  • $\begingroup$ That makes sense, as I was typing out my explanation I started to think of how there was a way for a counter example I just couldn't quite pinpoint it. The min capacity goes from 3 to 5. Correct? $\endgroup$
    – jam
    Mar 5, 2015 at 20:16
  • $\begingroup$ Yeah. The original min cut goes from 3 to 6, and then another cut goes from 4 to 5, becoming the new min cut. $\endgroup$
    – SE318
    Mar 5, 2015 at 21:24
  • $\begingroup$ Is there some sort of method used to figure this out or does it just come from intuition? $\endgroup$
    – jam
    Mar 6, 2015 at 3:02
  • 1
    $\begingroup$ Hmm... good question. I wouldn't say there is a method here, but... let me try to explain my thought process on seeing this problem: At first, it seemed rather intuitive to just say "oh yeah, that is true", but of course, one's first intuition isn't always right, so I started to consider exactly how adding one to each capacity affects each cut. Specifically I realized it would increase the capacity of the cut by the size of the cut. With that in mind, I knew I just needed to create cuts of different sizes, then pick numbers that would work well in order to produce a counter-example. $\endgroup$
    – SE318
    Mar 6, 2015 at 3:34
1
$\begingroup$

In such questions it's usually easier to visualize the counterexamples in term of set of arcs. What i mean can be better understood by the following pic.Counterexample easy thinking

Assume this are the capacities and source can send as much as needed, after adding +1 to all arcs capacities, we can see that the previous min-cut is no longer the min-cut (cos capacity has increased to 10), And one can see that the min cut will be between the Set of nodes in S2 and the sink. Many such questions are easily solved by this way of thinking. Hope it helps.

$\endgroup$
1
  • 1
    $\begingroup$ oh my oh my that is some serious drawing in here $\endgroup$
    – Anton Kr
    Jun 23, 2018 at 14:26

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.