How Does the Ford-Fulkerson Algorithm Determine Maximum Flow in a Network?

[Pietjuh]

Most of you have probably all heard of the max-flow min-cut theorem in graph theory. It says that in a network G=(V,A), the value of a maximum flow equals the capacity of a minimum cut. Then there is the Ford and Fulkerson algorithm to find a maximum flow in a network.

For the ones that don't really remember anymore how the algorithm works, i shall give a short summary:

1. Start with zero flow (x=0)
   
2. Construct a directed graph $$N_x=(V,A_x)$$ where $$A_x$$
   is defined to be the union of two sets, $$B_1 = \{(i,j)\, |\, (i,j)\in A\, x_{ij} < b_ij\}$$ and $$B_2 = \{ (j,i)\, |\, (i,j)\in A\, x_{ij} > 0 \}$$, where $$x_{ij}$$ is the flow between vertex i and j, and $$b_{ij}$$ is the capacity of the branch between i and j. The arrows in the first set are called forward arrows, and in the second set backward arrows. Choose a path P from vertex 1 to n. If it doesn't exist, go the the last step.
   
3. Determine $$\Delta = min(\Delta_1, \Delta_2)$$, $$\Delta_1 = min\{b_{ij} - x_{ij}\,|\, (i,j)\in B_1\}$$, $$\Delta_2 = min\{x_{ij}\,|\, (j,i) \in B_2\}$$
   
4. Add $$\Delta$$ to $$x_{ij}$$ if (i,j) is a forward arrow of P, and substract it if (j,i) is a backward arrow of P and do nothing if (i,j) or (j,i) isn't an arrow of P.
5. Go to step 2
6. x is a maximal flow

Now I am wondering if we could adapt this algorithm a bit, to also find an arrow in G, if it exists, which has the property that when the capacity of the arrow is raised, the value of the maximum flow is raised. Here's my idea. I hope it will be correct, or that you will have some better ideas how to solve it!

In every iteration there will be added an amount of $$\Delta$$ to the flow, which is the minimum of $$\Delta_1$$ and $$\Delta_2$$. First determine if this minimum lies in $$\Delta_1$$ or in the other. If it lies in $$\Delta_2$$, changing the capacity will not have any effect. If it lies in $$\Delta_1$$ we can raise the capacity of that particulary branch (i,j) to the point that it not exceeds the minimum value of $$\Delta_2$$. Now let's store this branch in a set called, say F. Isn't it true that when we finish with the algorithm, every branch in F has the property that when it's capacity is raised, the maximum flow will be higher?

 

[philosophking]

When you go and change the capacities like that, aren't you destroying your notion of "min-cut", so you'd have to go back and change things around? Maybe I'm not completely understanding the theorem.

 

[tacman]

Yes, it is true that every branch in F will have the property that when its capacity is raised, the maximum flow will be higher. This is because in every iteration of the algorithm, we are choosing the minimum value between \Delta_1 and \Delta_2, which means that for a branch to be included in F, its capacity must have been the minimum value in that iteration. Therefore, raising its capacity will result in a higher maximum flow.

However, it is important to note that this does not guarantee that raising the capacity of any branch in F will result in the overall maximum flow being increased. It only guarantees that the maximum flow will be increased if the capacity of that particular branch is raised. There could be other branches in the network that also have this property but are not included in F.

In order to find the branch that, when its capacity is raised, will result in the overall maximum flow being increased, we would need to consider all possible combinations of raising the capacities of different branches and choose the one that results in the highest maximum flow. This would require a more complex algorithm and would not be as efficient as the original Ford and Fulkerson algorithm.

Overall, your idea is correct and could potentially be useful in certain cases. However, it may not always guarantee finding the branch that will result in the highest maximum flow.