Max Flow Linear time algorithm, Find a valid flow

Question

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.

Answer 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?