Question

In a particular flow network G = (V,E) with integer edge capacities ce, we have already found the maximum s-t flow. However, we made a mistake in the capacity values of edge (u, v): we used cuv but the capacity is only cuv − 1. Moreover, the max flow f uses edge (u, v) at full capacity. Can you find a new optimal flow faster than by recomputing max flow in G?

Answer 1

Check the explanation

Explanation:

1) Algorithm for finding the new optimal flux: 1. Let E' be the edges eh E for which f(e)>O, and let G = (V,E). Find in Gi a path Pi from s to u and a path
`P_1`, from v to t.

2) [Special case: If
`P_1`, and
`P_2` have some edge e in common, then Piu[(u,v)}uPx has a directed cycle containing (u,v). In this instance, the flow along this cycle can be reduced by a single unit without any need to change the size of the overall flow. Return the resulting flow.]

3) Reduce flow by one unit along
`P_1U{(u,v)}UP_2`

4) Run Ford-Fulkerson with this sterling flow.

Justification and running time: Say the original flow has see F. Lees ignore the special case (4 After step (3) Of the elgorithuk we have a legal flaw that satisfies the new capacity constraint and has see F-1. Step (4). FOrd-Fueerson, then gives us the optimal flow under the new cePacie co mint. However. we know this flow is at most F, end thus Ford-Fulkerson runs for just one iteration. Since each of the steps is linear, the total running time is linear, that is, O(lVl + lEl).