3

So let me explain the question:

You are given a graph. You find the max flow. But it turns out that an edge, e_i, had the wrong capacity. It had one less. Unfortunately, the flow was maxed out at the old capacity.

Compute the new max flow in linear time (in terms of the number of edges and vertices) once you are told e_i had the wrong capacity.

Here's my plan: (1) You can't only drop the flow at edge e_i by one at an edge because you must violate certain constraints: like flow is conserved at an edge. Fix the flows so you can get a valid flow. But how?

(2) Someone has given me a hint: it will be helpful to show the valid flow = previous flow -1.mmm...

Help.

user678392
  • 1,981
  • 3
  • 28
  • 50

1 Answers1

1

Here's a couple of tips:

  1. Suppose you found a path with nonzero flow (i.e >= 1), and contained this edge e_i. How might you use this path to make the overall flow valid again? Now, suppose you aren't given this path. How might you get it yourself?
  2. Now, you know that the max flow of the new graph is either the same, or one less than before (why?). How might you find out which in linear time?
Dennis Meng
  • 5,109
  • 14
  • 33
  • 36
  • (1) This is the very exact thing I don't understand, and for (2) why is the max flow of the new graph be the same or one less than before? – user678392 Sep 17 '13 at 04:21
  • Which part of #1 are you stuck on? 2 builds on 1, so if you can't get 1 yet, don't worry about 2. – Dennis Meng Sep 17 '13 at 05:26
  • So I know WHY you can't just decrement the capacity in this case (might violate constraints). I just don't see how you can in linear time "repair" the flow. Also, thanks. – user678392 Sep 17 '13 at 13:34
  • @user678392 You know that you must drop the flow on e_i (otherwise you exceed its capacity), and you know that you can't only drop at that edge (because you'd violate flow constraints). So, where else would you have to drop some flow to make it valid again? – Dennis Meng Sep 17 '13 at 15:25
  • You can either drop the flow by one coming into the node or you can try to push one more unit of flow into an edge leaving the node in question. So if you take the first option, you have to drop the flow going back all the way to the front; if second, increase the flow by one all the way to the sink. If correct, is this done in linear time? – user678392 Sep 17 '13 at 15:27
  • Pushing doesn't help if you're already violating capacity constraints (It also doesn't help if it causes you to violate capacity constraints). Elaborate on what you mean by "drop the flow by one coming into the node", since that can mean different things in different contexts. It sounds like you're looking at this from a preflow-push standpoint, but I'm trying to get you to look at this from an augmenting flow standpoint. – Dennis Meng Sep 17 '13 at 16:45
  • Since the flow was maxed out, the edge in the residual graph is going in the opposite direction at. How does this help me? Forget what I said earlier. There is no way for what I was thinking to be linear. – user678392 Sep 17 '13 at 17:12
  • let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/37540/discussion-between-dennis-meng-and-user678392) – Dennis Meng Sep 17 '13 at 17:13