The Max Flow Problem

The next lessons discuss algorithms that solve flow problems in weighted graphs. Apart from direct applications in flow networks, they can also be applied to solve various kinds of matching or assignment problems.

Example of a flow network

As an example, let’s consider the problem of transferring a large file on the internet from London to Frankfurt. We want to achieve the maximum possible throughput in doing so. On the way, we may need to pass several intermediate nodes, and each connection we use on the way has a limited data rate.

This situation can be modeled as a weighted graph where the edge weights correspond to the maximum throughput on each connection, for example,. in Megabit per second:

Naturally, we’d like to utilize each connection at its full capacity. However, this is not always possible. For example, the outgoing connections from Amsterdam have a total capacity of 7 Mb/s, but the only incoming connection has a capacity of only 5 Mb/s, so the outgoing connections cannot be fully utilized.

The maximum network flow which can be achieved in this network is 10 Mb/s. There are actually several ways to obtain this maximum flow. The following image shows one of them:

The maximum flow problem

Let’s come up with a formalization of the flow maximization problem. The setting is a directed graph $G = (V, E, c)$, called a flow network, where $c : E \to \mathbb{N}$ is a weight function. The edge weights are the capacities of the edges, written as $c(u, v)$.

The capacity of an edge is the maximum flow that can be pushed through that single edge. We assume that the capacities are integers, and only an integer amount of flow can be pushed through an edge.

There are also two special nodes in $V$ ...