Max Flow Linear time algorithm, Find a valid flow

3
votes

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.

1
algorithmgraphmaxford-fulkersonedmonds-karp
Once you prove that, you can just get rid of one unit of flow, (albeit repeatedly until you reach a source, but in O(e)). That hint (2) solves your problem (1) nicely. – clwhisk
@clwhisk what does "that" refer to? – user678392
It seems like we are trying to solve a harder in order to solve an easier one. – user678392
that hint, the condition of that hint – clwhisk
See www2.cs.duke.edu/courses/summer11/cps130/files/… – ggorlen

1 Answers

1
votes

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?