What is the difference between maximal flow and maximum flow?

Question

What is the difference between maximal flow and maximum flow. I am reading these terms while working on Ford Fulkerson algorithms and they are quite confusing. I tried on internet, but couldn't get a reasonable answer. I believe maximum flow is quite clear as it means maximum amount of flow that can be transferred from source to sink in a network, but what exactly is maximal flow.

Please answer in layman terms if possible.

Thanks.

Answer 1

Short answer:

Think about the top of the mountains, each of them is a maximal solution, there is not place nearby that is higher than them, but only the top of the Everest mountain has the maximum height and is therefore the maximum solution.

Longer answer:

Let me explain it in geometric terms: think about a plane (e.g. a large peace of paper). Each point on the plane is a possible solution for the problem. The height of each point is the quality of the solution corresponding to that point. In optimization we want to find the optimal solution, i.e. the highest point on the plane. One idea to find the optimal solution is to start from a possible solution in the plane and improve it little by little: each time we move from a point to one near it which is higher. This is called a local search algorithm. This process stops when we reach a point which is higher than all points near it. Such a point is called a local optimum. The corresponding solution is called maximal as we cannot increase the quality of the solution by moving to any solution near it. However, a maximal solution doesn't need to be the optimal solution, it is optimal in comparison to its neighbors.

There are common conditions which if satisfied we will not have local optimals on the plane which are not globally optimals. In such situations we can use local search algorithms to find the optimal solution. One such condition is if the plane of solutions is convex, intuitively for every two points we have all points on the line connection them also in the solution space and the quality of each of them can be determined from the relative distance of the point to the two endpoints and the quality of the two endpoints. Optimization over convex spaces is studied in convex optimization.

Now, lets go back to the max flow problem. Fix a graph as input. Think of each flow that satisfies the capacity and preservation of flow requirements as a point. We call these valid flows. We want to find a maximum flow. Two points are near each other if we can obtain one by increasing or decreasing the flow through a path from the source to the sink.

We can start by the flow where the flow on all edges are zero (this is a valid flow). At each step we find a path from the source to the sink in the updated remaining capacity graph (the weight of each edge is the amount of its capacity that is not being used) somehow (e.g. using BFS) and increase the flow by adding this. This gives us a local search algorithm. The problem is that the space of solutions is not convex and we may end up with a flow that we cannot increase any more but it is not a maximum flow.

What can we do? One idea is to change the space of solutions to a convex one. For intuition think about a star on a plane. The points inside the star do not make a convex space but we can turn it into a convex space by including more points in our solution space and turning it into a pentagon.

This is essentially what we do by consider the existing flow on the original edges of the graph as new edges (called residual edges) where flow over them corresponds to decreasing the existing flow on the original edges. This makes the space convex and our local search algorithm does not get stuck on solutions which are locally optimal but not globally optimal.