Question

In a particular network G = (V, E) whose edges have integer capacities c_e, we have already found the maximum flow f from node to node t. However, we now find out that one of the capacity values we used was wrong: for edge (u, v) we used c_uv whereas it should have been c_uv. -1 This is unfortunate because the flow f uses that particular edge at full capacity: f = c.

We could redo the flow computation from scratch, but there’s a faster way. Show how a new optimal flow can be computed in$\mathit{O}\mathbf{(}\left|V\right|\mathbf{+}\left|E\right|\mathbf{)}$ time.

Short answer

The flow that meets the new capacity restriction and has size F - 1. Under the new capacity limit, it has its optimal flow.

Step-by-step solution

Algorithm for finding the new optimal flow

1. Let E' be the edges $e\in E$ which F(e) > 0, and let G' = (V,E'). Find in G' a path P₁ from s to u and a path P₂ from v to t.
2. [Special case: If P₁ from P₂ have some edge in common, then role="math" localid="1659793051037" $e\in E{P}_1\cup \left\{\left(u,v\right)\right\}\cup P_2$has a directed cycle containing (u,v). In this case, the flow along this cycle can be reduced by one unit without changing the size of the overall flow. Return the resulting flow.]
3. Reduce flow by one unit along $P_1\cup \left\{\left(u,v\right)\right\}\cup P_2$.
4. Run Ford-Fulkerson with this starting flow.
5. Flow start base on reduce unit and changing size of overall flow.

Step  2: Justification and running time

This source circulation had size F, as evidenced by the explanation and running time. Let's overlook the unique circumstance (2).

We have a valid flow that fulfils the new capacity limit and has size F - 1 during step (3) of the procedure. Its ideal flow underneath the new capacity limit is then determined by step (4), Ford-Fulkerson.

Therefore, the stream is at most F, Ford-Fulkerson only runs for one iteration. Because each step is shorter, the overall running time is linear $O(\left|\mathrm{V}\right|+\left|\mathrm{E}\right|)$.