13 The Max Flow Problem
This section introduces the max flow problem.
Objectives. After learning this material, you should be able to:
- State the format of an input to the max flow problem.
- Define when a function is a valid flow in the graph.
- Define the amount of flow and the max flow.
13.1 Motivation and input
We have already looked at finding paths in a graph. What if we want to route a large amount of traffic across a graph, such as packets across a computer network? In this case, the traffic may need to take multiple routes at once. Each edge of the network can only handle so much traffic at once – the capacity of that edge. We’d like to figure out how to route the traffic so as to get the most possible across.
In the max flow problem, the input consists of:
- A directed graph \(G = (V,E)\),
- a source \(s \in V\) and sink \(t \in V\), and
- a capacity function \(c: E \to \mathbb{R}_{\geq 0}\).
We can also think of the capacity function as nonnegative edge weights. We extend \(c\) to be a function on all pairs of vertices, by defining \(c(u,v) = 0\) if \((u,v) \not\in E\). We will also make the following simplifying assumption, which isn’t necessary, but makes our lives a bit easier:
Assumption: no anti-parallel edges. We assume that if \((u,v) \in E\), then \((v,u) \not\in E\). In other words, there is only one edge between any pair of vertices.
13.2 Valid flows
Given the input, a potential solution is any method of routing flow from \(s\) to \(t\). But what does that mean, exactly? A function \(f: V \times V \to \mathbb{R}_{\geq 0}\) is called a flow, and the flow is valid if:
- (capacity constraint) \(f(u,v) \leq c(u,v)\) for all \(u,v \in V\). This implies that if there is no edge \((u,v)\), then \(f(u,v) = 0\).
- (flow constraint) for all vertices \(v \not\in \{s,t\}\), \(\sum_{u \in V} f(u,v) = \sum_{w \in V} f(v,w)\).
We illustrate the current flow compared to the capacity of the edge using the notation “flow/capacity”, e.g. 6/10.
Exercise 13.1 On the example graph of Figure 13.1 above, which of the following flows are valid? If invalid, indicate whether the flow or capacity constraint is violated. From now on, we will label each edge \((u,v)\) with a label of the form 5/9, where here \(5\) represents \(f(u,v)\) and 9 represents \(c(u,v)\). We have also put the flows in blue here for added emphasis.
Solution.
- Part a: valid.
- Part b: invalid. The flow constraint at \(w\) is violated: the total flow in is 3, but the total flow out is 5.
- Part c: invalid. The capacity constraint on \((v,t)\) is violated: \(c(v,t) = 2\), but \(f(v,t) = 4\).
13.3 Max flow
Given a flow \(f\), we define the amount of flow, written \(|f|\) for short, to be the following quantity:
\(|f| = \sum_{v \in V} f(v,t) - \sum_{w \in V} f(t,w)\).
In other words, the total amount of flow \(|f|\) is the net flow into the sink \(t\).
In the max flow problem, the output is:
- A valid flow \(f\) whose amount is maximized, over all possible valid flows.
Exercise 13.2 On the example graph of Figure 13.1, what is the max flow amount and what is the flow?
Solution
Here is a max flow \(f\). The amount of \(|f| = 10\). There are other slightly different flows that also have value \(10\) (can you find them?).
