Max Flow : A Deep Dive

Algorithm › Deep Dive

The Actual Problem

Given a flow network , find a feasible flow through the flow network that obtains the maximum possible flow rate .

In plain language , you are given a source and a sink in a flow network . You have to maximize the flow from source to sink .

Dumbest thing to do

Well , if you are like me the first solution that can come to your mind is something like this :

1
2
while there exists a path in the graph with bottlneck capacity > 0 :
    augment a flow through that path

Now , will it work ?

Spoiler

Okay , let’s try first atleast to see if it works . Here is an example graph :

What would you do if you were to solve greedily ?

  • You would find an arbitrary path that can go from s to t
  • Find the bottleneck value of this path and add to the flow . ( Not to mention that it has to be positive to add to the maximum flow )

But . look at this .

Imagine being a dumb guy like me and taking the _blue_ path as your first path . You are screwed .You can’t find anymore path with a bottlencek value > 0 . So you end up having Max Flow = 3 .

But if you were to take a different path you will be able to find larger answer than your current one . Here is an example of this case :

Here Max Flow = 5 . If you were to try out a few more possible order , you will see that this eventually is the maximum possible value .

So , The answer is _NO_ . You can not greedily solve the Maximum Flow Problem .

Although that’s the intuitive thing to do , this greedy approach will fail miserably .

So how do you solve ?

Now that we know we are really dumb to solve this problem . Let’s see how people over the past half century has solved this particular problem so that we can get an intuition for it .

The first persons to solve this problem is Ford ( not the guy who makes cars :p ) and Fulkerson . They came up with the concept of residual graph and basically did the greedy approach on that graph . The trick lies on how we create the residual graph .

Later Edmonds and Karp came up with a specialization of Ford-Fulkerson Algorithm by finding the augmenting paths needed in the Ford-Fulkerson Algorithm using BFS .

And later Dinic came up with a blocking flow algorithm ….

Ford Fulkerson Method (Not Algorithm)

In plain language , the algorithm is as follows :

1
2
while there exists a path in the residual graph with bottlneck capacity > 0 :
    augment a flow through that path

The reason why this is called method and not algorithm is that they did’t exactly specify how to find the augmenting paths :angry: ( aka the paths with bottleneck capacity > 0 )

Now , why does our dumb algorithm works when we apply that on Residual Graph and what the heck is even this residual graph ?

To answer that , we need to

  • First , go again to our dumb algorithm and see exactly what went wrong and was there a way to correct our dumb move . After all we learn from our mistakes : )
  • Second , build an intuition for why Residual Graph is build the way it is build .

First let’s start with the definition of Residual Graph ( to see why that does not initially makes a lot of sense )

We build the Residual Graph in such a way that :

  • If the edge belongs to the original graph (there is an edge u -> v ), we replace their value with their current capacity i.e Residual Capacity(u,v) = Total Capacity(u,v) - Flow(u,v) ( So far so good , this step seems to be the intuitive thing to do )
  • If the edge doesn’t belong to the original graph (there is no edge u -> v ) , we create an edge with the value equals to the flow in the opposite direction i.e Residual Capacity(u,v) = - Flow(v,u)

The last step doesn’t seem so intuitive . After all why would we add an edge that is not present in the original graph ? TO get an intuition for why we do that . Let’s answer a simple question :

1
Can reducing the flow in a network cause the overall flow to increase ?

The answer is quite counter intuitively YES .

The example graph is the same as the one prviously discussed . And in the same way , being a dumb guy like me you have made your first move wrong and currently screwed . What operation can you possibly do to unscrew ( I’m not sure if that is even a valid word :v ) yourself ?
If there was some way to go from b to a you can get another flow with value 2 using the path s -> b -> a -> t .
Imagine pushing an imaginary flow value of 2 to the opposite direction of edge a -> b . This negative flow will enduce a path s -> b -> a -> t . Although realistically there is no edge b -> a but adding an edge in the opposite direction is equivalent to reducing the flow through a -> b . This is what we did :

Thus , reducing the a -> b flow from 3 to 1 . We have indeed increased the maximum flow .

So , YES . Reducing the flow in a network can cause the overall flow to increase !

Hope you had your Eureka Moment after reading this far !

And in case you haven’t , the reason why we create the virtual edge in the opposite direction in the residual graph is that even if we have not taken the paths in proper order , we still have the option to reduce the flow by the virtual edge . That’s why we create the graph in this way

Complexity

O(E * F)

Ford Fulkerson Method doesn’t specify the method for finding augmenting paths . It can be done using BFS / DFS . Both has complexity O( E + V ) , here O(E) . And if all the flows are integers , then at the worst case for each augmenting path the flow of the network increases by at least 1 . So , complexity is O(E * F) where F is the maximal flow of the network .

Note

In case of rational capacities, the algorithm will also terminate, but the complexity is not bounded. In case of irrational capacities, the algorithm might never terminate , and might not even converge to the maximal flow.