Update Maximum Flow After Adding an Edge

Question

Consider we have a network flow and using Edmond-Karp algorithm, we already have the maximum flow on the network. Now, if we add an arbitrary edge (with certain capacity) to the network, what is the best way to update the maximum flow? I was thinking about updating the residual network regarding the new edge and again look for augmenting path until we find new max flow, but I am not sure if it works or if it is the best way!

Answer 1

After doing maxflow you know the amount of content each edge flowed.

So, when the cost of an edge changed you can do the following things :

1. Suppose, the content flowed by that edge is w.
2. Now do a forward dfs and a backward dfs from that edge and undone total w content from the edge it linked.

Here each edge is represented by x/y, where y means the edge capacity and x means the content it flowed.

Now you want to change the cost of edge 4->3 from 2 to 3.

All you have to do is do a forward and backward dfs from 4->3 edge and undone 2 weight from these edge as 4->3 flowed w=2 content.

Here is the process will look like :

Now you are almost done :)

3. Change the cost of the edge 4->3 from 2 to 3 and again try to find an augmenting path :)

Let me know if you find it difficult to understand or if i'm wrong somehow :)

Edit :

1. If new edge cost is greater than current cost than you won't have to undone the weight. You can just try to find an augmenting path changing the edge's capacity.

2. But if the capacity reduced, you have to undone the weight and try to find an augmenting path.

3. If a new edge added, you can just add the edge and try to find an augmenting path if available. that's it.

Answer 2

Actually adding a new edge is not very difficult - you have the flows/ capacities of the edges before adding the edge and then you add the edge and its inverse. Then run the algorithm you use to find augmenting path until you find non-zero flow and that's it. Most of the max flow will already have been found so this should(in theory) not be too slow. I do not know which max flow algorithm you are using so I can not be more specific, but it is possible that after adding the new edge you violate the property of the algorithm and thus you find the max flow in a sub-optimal way. Still you've already processed most of the graph so this should not be a too big problem.

I would recommend you to use Ford-Fulkerson algorithm to finish of the task no matter what the original algorithm you used for the max flow is. I think it will perform well in cases that most of the max flow is already discovered.