Maximum Flow Problem Statement
What you'll learn: How to formally define the problem of finding the largest possible flow from a source to a sink in a flow network.
Now that you understand flow networks, conservation, capacity constraints, and what makes a flow valid, we can state the optimization problem at the heart of network flow algorithms.
The Core Problem
Given a flow network with a source vertex s and a sink vertex t, the maximum flow problem asks: What is the maximum amount of flow we can push from s to t while respecting all capacity and conservation constraints?
Think of it like this: you have a water pipe network with a single water source and a single drain. Some pipes are narrow, some are wide (capacity limits). Water must flow continuously through junctions without accumulating (flow conservation). What's the maximum gallons per second you can deliver from source to drain?
Formal Statement
Find a valid flow f that maximizes the total flow value leaving the source (equivalently, entering the sink).
The flow value is the sum of all flow leaving s (or all flow entering t — they're equal by conservation). We want to maximize this single number while ensuring:
- No edge carries more than its capacity
- Every intermediate vertex conserves flow
Example Context
If your network represents a transportation system, the maximum flow tells you the maximum throughput. If it represents a communication network, it reveals bandwidth limits. If modeling supply chains, it identifies bottlenecks.
Key Takeaway: The maximum flow problem seeks the valid flow assignment that maximizes the total amount flowing from source to sink, subject to capacity and conservation constraints.