Search code examples
algorithmmax-flowford-fulkerson

How to update maximum flow models

I am trying to understand the answer to part b of this question. Specifically, I want to know why it is correct and how to prove that the time complexity is O(V+E). This is a hw problem and I found this answer online but I'm struggling to understand why it is correct and don't want to just copy it. Thank you very much!

Image of the problem

Solution

  • If the flow on the edge was 1 less than the capacity, the flow is still a valid maximum flow, and there's nothing to do.

    So let's look at the case where the flow now violates the capacity. Also, let's assume that the (original) network is connected, that is, there exists an s-t-path (otherwise the "max flow" would be just 0).

    The idea is basically to "undo" a (hypothetical) iteration of Ford-Fulkerson in order to get rid of the capacity violation, going back to a valid maximum flow, at the cost of one unit of flow.

    Let's look at the edge (u, v). Since we have a capacity violation, we have flow. This flow must come from s, so there is a s-u-path along which we have positive flow - at least one unit, because our flow is integer.

    Due to flow preservation, this unit must also reach the sink, so there's also a v-t-path with positive flow - again at least one unit - along the path. Overall this means there must be a s-t-path over (u, v) over which at least one unit of flow flows.

    You could find this path for example by running a BFS from u, following predecessors along edges with positive flow, to find a s-u-path, and running a BFS from v, following successors along edges with positive flow, to find a v-t-path. By using BFS, we can ensure that the two paths don't cross (if they did cross, we could cut out the part where they cross).

    We can reduce the flow along this path by 1. By doing so, we remove the capacity violation, but we may now have a suboptimal flow - perhaps there is an alternative way to send that unit of flow that doesn't use this edge.

    To fix this, you run another iteration with the new capacities and the now valid flow. If you find an augmenting path, you (can only) augment by exactly 1 unit (you can not augment by more, otherwise you would have a better solution than the supposedly optimal solution to the less constrained problem where the edge had more capacity).

    As for the time complexity:

    • Finding the s-t-path is O(V + E): You run 2 BFS's. A BFS has to look at every node and every edge in the worst case, so there is no way around this.
    • Finding an augmenting path, or determining that none exists, is also O(V + E), again the time complexity of BFS.