Maximum Flow

Chapter 1: Flow Networks

Before we can maximize flow, we need to define precisely what a flow network is and what rules flow must obey. A flow network is a directed graph G = (V, E) with two special vertices: a source s (where flow originates) and a sink t (where flow is consumed). Every edge (u, v) has a non-negative capacity c(u, v) ≥ 0. If edge (u, v) is not in E, we define c(u, v) = 0.

A flow in this network is a function f : V × V → R that assigns a real number to every pair of vertices, subject to two constraints.

Constraint 1: Capacity Constraint

For all u, v ∈ V:

You cannot send more flow through a pipe than its capacity allows. You also cannot send negative flow (that would mean flow is going backwards, which we handle differently via the residual graph in Chapter 2).

Constraint 2: Flow Conservation

For all u ∈ V − {s, t}:

For every vertex that is not the source or sink, the total flow coming in must equal the total flow going out. No flow is created or destroyed at intermediate nodes. Think of it as water flowing through junctions — what pours in must pour out.

The Value of a Flow

The value of a flow f, denoted |f|, is the total net flow leaving the source:

By flow conservation, this also equals the total net flow entering the sink. The maximum flow problem asks: find a flow f that maximizes |f| while respecting both constraints.

A Worked Example

Consider this network with 4 vertices {s, a, b, t} and 5 edges:

One valid flow: f(s,a)=8, f(s,b)=10, f(a,b)=0, f(a,t)=8, f(b,t)=10. Check conservation at a: in=8, out=8. At b: in=10, out=10. Value = 18. Can we do better? We could push f(s,a)=10, f(a,b)=2, f(a,t)=8, f(s,b)=10, f(b,t)=12. Check: at a, in=10, out=10. At b, in=10+2=12, out=12. Value = 20. This is the maximum.

python
# Flow network representation using adjacency dict
def create_flow_network():
    # capacity[u][v] = capacity of edge u->v
    capacity = {
        's': {'a': 10, 'b': 10},
        'a': {'b': 2, 't': 8},
        'b': {'t': 12},
        't': {}
    }
    # flow[u][v] = current flow on edge u->v
    flow = {u: {v: 0 for v in capacity[u]} for u in capacity}
    return capacity, flow

def flow_value(flow, source):
    """Total flow leaving the source."""
    return sum(flow[source].values())

def check_conservation(flow, node, all_nodes):
    """Check flow in == flow out at a node."""
    flow_in = sum(flow[u].get(node, 0) for u in all_nodes)
    flow_out = sum(flow[node].get(v, 0) for v in all_nodes)
    return flow_in == flow_out

Chapter 2: Ford-Fulkerson Method

We now know what a valid flow is. But how do we find the maximum flow? The Ford-Fulkerson method is a beautifully simple idea: keep finding paths from s to t that can carry more flow, and send flow along them, until no such path exists.

The magic ingredient is the residual graph. Given a flow network G and a flow f, the residual graph G_f tells us how much additional flow we can push through each edge — including the possibility of "undoing" flow we already sent.

Residual Capacity

For every pair of vertices u, v, the residual capacity is:

The forward residual is the remaining capacity on an edge — how much more you can push forward. The backward residual is the flow currently on an edge — how much you can "cancel" by pushing flow in the reverse direction. This is the key trick. By allowing backward edges in the residual graph, we let the algorithm correct suboptimal earlier decisions.

Augmenting Paths

An augmenting path is any path from s to t in the residual graph G_f where every edge has positive residual capacity. The bottleneck of this path is the minimum residual capacity along it — this is how much additional flow we can send.

The Algorithm

Worked Example: Step by Step

Network: s → a (cap 10), s → b (cap 10), a → b (cap 2), a → t (cap 8), b → t (cap 12).

Iteration 1: Find path s → a → t. Residual caps: s→a is 10, a→t is 8. Bottleneck = 8. Send 8 units. Now f(s,a)=8, f(a,t)=8. Residual: s→a has 2 left, a→t has 0 left (saturated), backward edges a→s=8 and t→a=8 appear.

Iteration 2: Find path s → b → t. Residual caps: s→b is 10, b→t is 12. Bottleneck = 10. Send 10. Now f(s,b)=10, f(b,t)=10. Total flow = 18.

Iteration 3: Find path s → a → b → t. Residual caps: s→a is 2, a→b is 2, b→t is 2. Bottleneck = 2. Send 2. Now f(s,a)=10, f(a,b)=2, f(b,t)=12. Total flow = 20.

Iteration 4: No more augmenting paths (s→a is 0, s→b is 0). Done. Maximum flow = 20.

python
from collections import defaultdict

def ford_fulkerson(graph, source, sink):
    """
    graph: dict of dict, graph[u][v] = capacity
    Returns: max flow value, flow dict
    """
    # Build adjacency with reverse edges for residual graph
    capacity = defaultdict(lambda: defaultdict(int))
    for u in graph:
        for v in graph[u]:
            capacity[u][v] = graph[u][v]

    flow = defaultdict(lambda: defaultdict(int))
    max_flow = 0

    def dfs(node, target, visited, bottleneck):
        """Find augmenting path via DFS, return bottleneck."""
        if node == target:
            return bottleneck
        visited.add(node)
        for neighbor in capacity:
            residual = capacity[node][neighbor] - flow[node][neighbor]
            if residual > 0 and neighbor not in visited:
                pushed = dfs(neighbor, target, visited, min(bottleneck, residual))
                if pushed > 0:
                    flow[node][neighbor] += pushed
                    flow[neighbor][node] -= pushed  # reverse edge
                    return pushed
        return 0

    while True:
        pushed = dfs(source, sink, set(), float('inf'))
        if pushed == 0:
            break
        max_flow += pushed

    return max_flow, flow

# Example usage
G = {'s': {'a': 10, 'b': 10}, 'a': {'b': 2, 't': 8}, 'b': {'t': 12}, 't': {}}
result, flows = ford_fulkerson(G, 's', 't')
print(f"Max flow: {result}")  # Max flow: 20

Chapter 3: Edmonds-Karp

Ford-Fulkerson says "find any augmenting path." But which path should we pick? DFS wanders deep into the graph and might find a long, winding path with a tiny bottleneck. What if we always picked the shortest augmenting path (fewest edges)?

That single change — use BFS instead of DFS to find augmenting paths — transforms Ford-Fulkerson into the Edmonds-Karp algorithm. The runtime becomes O(VE²), completely independent of the maximum flow value. This is a polynomial guarantee that DFS-based Ford-Fulkerson lacks.

Why BFS Gives a Polynomial Bound

The key insight: when we use BFS, the shortest-path distance from s to any vertex v in the residual graph never decreases across iterations. It can only stay the same or increase. This is called the monotonicity lemma.

Why does this help? Each augmenting path saturates at least one edge (the bottleneck). Once an edge is saturated, the shortest-path distance to its endpoints must increase by at least 2 before that edge can become unsaturated again (via a backward edge). Since shortest paths can increase at most V times, each edge can be a bottleneck at most V/2 times. There are at most E edges. So the total number of augmentations is at most O(VE). Each BFS takes O(E). Total: O(VE · E) = O(VE²).

Worked Example: BFS vs DFS

Consider: s → a (cap 1000), s → b (cap 1000), a → b (cap 1), a → t (cap 1000), b → t (cap 1000). Max flow = 2000.

DFS worst case: If DFS alternately finds s→a→b→t and s→b→a→t (using the a↔b edge and its reverse), each sending only 1 unit, it takes 2000 iterations.

BFS (Edmonds-Karp): BFS finds s→a→t (length 2) first, sends 1000. Then s→b→t (length 2), sends 1000. Done in 2 iterations.

python
from collections import defaultdict, deque

def edmonds_karp(graph, source, sink):
    """Edmonds-Karp: Ford-Fulkerson with BFS. O(VE^2)."""
    capacity = defaultdict(lambda: defaultdict(int))
    adj = defaultdict(set)  # adjacency list for BFS
    for u in graph:
        for v, cap in graph[u].items():
            capacity[u][v] += cap
            adj[u].add(v)
            adj[v].add(u)  # reverse edge for residual

    flow = defaultdict(lambda: defaultdict(int))
    max_flow = 0

    while True:
        # BFS to find shortest augmenting path
        parent = {source: None}
        queue = deque([source])
        while queue and sink not in parent:
            u = queue.popleft()
            for v in adj[u]:
                residual = capacity[u][v] - flow[u][v]
                if residual > 0 and v not in parent:
                    parent[v] = u
                    queue.append(v)

        if sink not in parent:
            break  # no augmenting path

        # Trace path and find bottleneck
        bottleneck = float('inf')
        v = sink
        while parent[v] is not None:
            u = parent[v]
            bottleneck = min(bottleneck, capacity[u][v] - flow[u][v])
            v = u

        # Augment flow along path
        v = sink
        while parent[v] is not None:
            u = parent[v]
            flow[u][v] += bottleneck
            flow[v][u] -= bottleneck  # maintain skew symmetry
            v = u

        max_flow += bottleneck

    return max_flow

Chapter 4: Max-Flow Min-Cut Theorem

The max-flow min-cut theorem is one of the most beautiful results in combinatorial optimization. It says that the maximum amount of flow you can push through a network equals the minimum capacity of edges you need to cut to completely disconnect the source from the sink. Two seemingly different optimization problems have the same answer.

What Is a Cut?

An s-t cut (S, T) is a partition of the vertices into two sets S and T such that s ∈ S and t ∈ T. The capacity of the cut is the total capacity of edges crossing from S to T:

Think of it as: if you severed every edge from S to T, no flow could reach the sink. The capacity of the cut is the "cost" of severing those edges. A minimum cut is the s-t cut with the smallest capacity.

Note: edges from T to S do not count toward the cut capacity. This is asymmetric — only edges going from the source side to the sink side matter.

The Theorem

The following three statements are equivalent:

Proof Sketch

(1 ⇒ 2): If f is maximum and there exists an augmenting path, we could increase the flow — contradiction.

(2 ⇒ 3): If there is no augmenting path, define S = {vertices reachable from s in G_f} and T = V − S. Since t is not reachable, t ∈ T. For any edge (u, v) with u ∈ S, v ∈ T: the residual capacity c_f(u, v) = 0 (otherwise v would be reachable). This means f(u, v) = c(u, v) — every forward edge across the cut is saturated. And for any edge (v, u) with v ∈ T, u ∈ S: f(v, u) = 0 (otherwise the backward edge would make v reachable from S). So the net flow across the cut equals ∑ c(u, v) = c(S, T).

(3 ⇒ 1): For any flow f and any cut (S, T), the net flow across the cut equals |f| (by flow conservation — what leaves S must equal what leaves s). Since f(u, v) ≤ c(u, v) for each edge, |f| ≤ c(S, T). If |f| = c(S, T), then f is maximum (no flow can exceed any cut capacity).

Finding the Min Cut

After running max flow (e.g., Edmonds-Karp), the min cut falls out for free:

python
def find_min_cut(graph, source, sink):
    """Find min cut after running max flow."""
    # First, compute max flow (reuse Edmonds-Karp internals)
    capacity = defaultdict(lambda: defaultdict(int))
    adj = defaultdict(set)
    for u in graph:
        for v, cap in graph[u].items():
            capacity[u][v] += cap
            adj[u].add(v)
            adj[v].add(u)
    flow = defaultdict(lambda: defaultdict(int))

    # Run Edmonds-Karp (same as before)...
    max_flow = 0
    while True:
        parent = {source: None}
        queue = deque([source])
        while queue and sink not in parent:
            u = queue.popleft()
            for v in adj[u]:
                if capacity[u][v] - flow[u][v] > 0 and v not in parent:
                    parent[v] = u
                    queue.append(v)
        if sink not in parent: break
        bottleneck = float('inf')
        v = sink
        while parent[v] is not None:
            u = parent[v]; bottleneck = min(bottleneck, capacity[u][v] - flow[u][v]); v = u
        v = sink
        while parent[v] is not None:
            u = parent[v]; flow[u][v] += bottleneck; flow[v][u] -= bottleneck; v = u
        max_flow += bottleneck

    # BFS from source in residual graph to find S
    S = set()
    queue = deque([source])
    S.add(source)
    while queue:
        u = queue.popleft()
        for v in adj[u]:
            if v not in S and capacity[u][v] - flow[u][v] > 0:
                S.add(v)
                queue.append(v)

    # Min cut edges: (u,v) where u in S, v not in S, and capacity > 0
    cut_edges = []
    for u in S:
        for v in adj[u]:
            if v not in S and capacity[u][v] > 0:
                cut_edges.append((u, v, capacity[u][v]))

    return max_flow, S, cut_edges

Chapter 5: Bipartite Matching

This is the payoff chapter. Everything we have learned — flow networks, Ford-Fulkerson, residual graphs, max-flow min-cut — comes together to solve one of the most practical problems in computer science: bipartite matching.

The Problem

You have 5 students and 5 projects. Each student is interested in some subset of projects. Assign students to projects so that (1) each student gets at most one project, (2) each project is assigned to at most one student, and (3) the total number of assigned pairs is maximized. This is the maximum bipartite matching problem.

A bipartite graph is a graph whose vertices can be divided into two sets L (left) and R (right) such that every edge goes from L to R. There are no edges within L or within R. A matching is a set of edges where no vertex appears more than once. A maximum matching is a matching with the most edges possible.

Reduction to Max Flow

Here is the brilliant reduction: transform the bipartite matching problem into a max flow problem.

Why this works: Capacity 1 on all edges means each student (left vertex) can be "used" at most once (s sends at most 1 unit to each L vertex) and each project (right vertex) can absorb at most 1 unit (each R vertex sends at most 1 to t). Flow conservation ensures each unit of flow represents a single student-project assignment. Max flow maximizes the total assignments.

The Big Simulation

This is the showcase simulation. You have students on the left and projects on the right. Click pairs to add edges (interest connections). Then click "Find Matching" to run max flow and see the maximum matching highlighted. Try adding and removing edges to see how the matching changes.

python
def max_bipartite_matching(left, right, edges):
    """
    left: list of left vertices (students)
    right: list of right vertices (projects)
    edges: list of (u, v) where u in left, v in right
    Returns: list of matched (u, v) pairs
    """
    # Build flow network
    graph = defaultdict(lambda: defaultdict(int))
    adj = defaultdict(set)
    s, t = '__source__', '__sink__'

    for u in left:
        graph[s][u] = 1
        adj[s].add(u); adj[u].add(s)
    for v in right:
        graph[v][t] = 1
        adj[v].add(t); adj[t].add(v)
    for u, v in edges:
        graph[u][v] = 1
        adj[u].add(v); adj[v].add(u)

    # Run Edmonds-Karp
    flow = defaultdict(lambda: defaultdict(int))
    max_flow = 0
    while True:
        parent = {s: None}
        queue = deque([s])
        while queue and t not in parent:
            u = queue.popleft()
            for v in adj[u]:
                if v not in parent and graph[u][v] - flow[u][v] > 0:
                    parent[v] = u; queue.append(v)
        if t not in parent: break
        v = t
        while parent[v] is not None:
            u = parent[v]
            flow[u][v] += 1; flow[v][u] -= 1
            v = u
        max_flow += 1

    # Extract matched pairs
    matching = []
    for u in left:
        for v in right:
            if flow[u][v] > 0:
                matching.append((u, v))
    return matching

# Example
students = ['Alice', 'Bob', 'Carol', 'Dave']
projects = ['ML', 'Web', 'DB', 'OS']
interests = [('Alice','ML'), ('Alice','Web'), ('Bob','ML'),
             ('Bob','DB'), ('Carol','Web'), ('Dave','OS')]
result = max_bipartite_matching(students, projects, interests)
print(result)  # e.g. [('Alice','Web'), ('Bob','ML'), ('Carol','Web'?), ('Dave','OS')]

Konig's Theorem

In a bipartite graph, the size of the maximum matching equals the size of the minimum vertex cover (the smallest set of vertices that touches every edge). This is the bipartite version of max-flow min-cut, and it follows directly from it. The min cut in our flow network corresponds to a minimum vertex cover.

Chapter 6: Applications

Max flow is a universal tool. Dozens of problems that look nothing like "pushing water through pipes" can be reduced to max flow. The art is recognizing the reduction. Here are six classic applications, each with its reduction explained.

1. Image Segmentation

You have an image. Each pixel should be classified as "foreground" or "background." For each pixel i, you have a likelihood score f_i (how likely it is foreground) and b_i (how likely it is background). Adjacent pixels that get different labels incur a penalty p_ij (because natural images have smooth regions).

Reduction: Create a flow network. Source = foreground, sink = background. For each pixel i: edge from s to i with capacity f_i, edge from i to t with capacity b_i. For each pair of adjacent pixels i, j: edges (i, j) and (j, i) each with capacity p_ij. The minimum cut assigns each pixel to S (foreground) or T (background), minimizing the total cost of misclassified pixels plus boundary penalties.

2. Baseball Elimination

Can team X still win the league? This seemingly simple question has a surprisingly elegant max-flow solution. If every team that could possibly overtake X has to play each other, and there is not enough "capacity" for them to all lose enough games, then X is eliminated.

Reduction: Source connects to game-nodes (each remaining game between two teams). Each game-node connects to the two teams playing, with capacity ∞ (someone must win). Each team connects to the sink with capacity = max(wins X can finish with) − current wins of that team. If max flow does not saturate all source edges, team X is eliminated.

3. Airline Scheduling

An airline has a set of flight legs that must be flown. Each leg has a departure airport, arrival airport, and time. What is the minimum number of airplanes needed to fly all legs? This reduces to bipartite matching: create a node for each leg, connect leg i to leg j if the same plane could fly leg i then leg j (arrival of i is at same airport as departure of j, with enough turnaround time). Maximum matching = maximum number of legs that can share planes. Minimum planes = total legs − max matching.

4. Network Reliability

Given a communication network, what is the minimum number of edges whose failure disconnects two specific nodes? By the max-flow min-cut theorem (with all capacities = 1), this equals the maximum number of edge-disjoint paths between the two nodes. More disjoint paths = more reliable.

5. Project Selection (Max Weight Closure)

You have a set of projects. Each project has a profit (positive or negative). Some projects depend on others (if you do project A, you must also do project B). Select a subset of projects to maximize total profit, respecting all dependencies. This is the max weight closure problem, solvable via min cut.

6. Survey Design

You need to assign interviewers to respondents. Each interviewer can handle at most k interviews. Each respondent needs exactly one interview. Interviewers have preferences (will only interview certain respondents). This is bipartite matching with degree constraints — directly a max flow problem.

Chapter 7: Advanced Algorithms

Edmonds-Karp at O(VE²) is good, but for large graphs (millions of vertices), we need faster algorithms. Three major improvements dominate practice.

Dinic's Algorithm — O(V²E)

Dinic's algorithm (1970) improves on Edmonds-Karp by finding multiple augmenting paths at the same distance before increasing the distance. The key concepts:

Level graph: After BFS, assign each vertex its BFS distance from s. The level graph contains only edges (u, v) where level(v) = level(u) + 1. This prunes backward and sideways edges, leaving only "forward progress" edges.

Blocking flow: A flow in the level graph is "blocking" if every path from s to t in the level graph has at least one saturated edge. You find a blocking flow by doing multiple DFS passes through the level graph, using a "current edge" pointer that avoids re-exploring dead ends. This takes O(VE) per phase.

Phases: Each phase does one BFS (build level graph) + one blocking flow. After a blocking flow, the shortest-path distance increases by at least 1. Since the shortest path can be at most V, there are at most V phases. Total: O(V · VE) = O(V²E).

Push-Relabel — O(V²E) or O(V³)

Push-relabel (Goldberg & Tarjan, 1988) takes a completely different approach. Instead of finding augmenting paths from s to t, it works locally:

Preflow: Unlike a flow, a preflow allows vertices to have more incoming flow than outgoing (creating "excess"). The source pushes as much flow as possible onto its neighbors. Each vertex then tries to push excess forward toward the sink.

Height function: Each vertex has a "height" h(v). Flow can only be pushed downhill: from u to v if h(u) = h(v) + 1. If a vertex has excess but no lower neighbor with residual capacity, it relabels (increases its height) to find one.

Operations: Push(u, v) sends min(excess(u), residual(u,v)) from u to v. Relabel(u) sets h(u) = 1 + min(h(v)) over all v with residual(u,v) > 0. Keep pushing and relabeling until no vertex (except s and t) has excess.

The basic algorithm runs in O(V²E). With the "highest label" heuristic (always process the vertex with the highest excess), it runs in O(V²√E). With the "gap relabeling" optimization, it is O(V³) in the worst case but extremely fast in practice — often faster than Dinic's on dense graphs.

Min-Cost Max-Flow

What if each edge has both a capacity and a cost per unit of flow? The min-cost max-flow problem finds the maximum flow with the minimum total cost. This is solved by replacing BFS (find shortest by hops) with Bellman-Ford or SPFA (find shortest by cost) in the augmenting-path algorithm. Each augmentation uses the cheapest available path.

Applications: assigning workers to jobs where each assignment has a different productivity (min-cost max bipartite matching), transportation problems, and network design.

When to Use Which

python
def dinic(graph, source, sink):
    """Dinic's algorithm. O(V^2 E)."""
    capacity = defaultdict(lambda: defaultdict(int))
    adj = defaultdict(set)
    for u in graph:
        for v, cap in graph[u].items():
            capacity[u][v] += cap
            adj[u].add(v); adj[v].add(u)

    flow = defaultdict(lambda: defaultdict(int))
    all_nodes = set(adj.keys())

    def bfs_levels():
        """BFS to build level graph. Returns level dict or None."""
        level = {source: 0}
        queue = deque([source])
        while queue:
            u = queue.popleft()
            for v in adj[u]:
                if v not in level and capacity[u][v] - flow[u][v] > 0:
                    level[v] = level[u] + 1
                    queue.append(v)
        return level if sink in level else None

    def dfs_block(u, pushed, level, iterators):
        """DFS to find blocking flow using current-edge optimization."""
        if u == sink:
            return pushed
        while True:
            try:
                v = next(iterators[u])
            except StopIteration:
                return 0
            if level.get(v, -1) == level[u] + 1:
                residual = capacity[u][v] - flow[u][v]
                if residual > 0:
                    d = dfs_block(v, min(pushed, residual), level, iterators)
                    if d > 0:
                        flow[u][v] += d; flow[v][u] -= d
                        return d
        return 0

    max_flow = 0
    while True:
        level = bfs_levels()
        if level is None: break
        iterators = {u: iter(adj[u]) for u in all_nodes}
        while True:
            pushed = dfs_block(source, float('inf'), level, iterators)
            if pushed == 0: break
            max_flow += pushed

    return max_flow

Chapter 8: Interview Arsenal

Max flow problems in interviews come in two flavors: (1) implement Ford-Fulkerson / Edmonds-Karp from scratch, and (2) recognize that a problem reduces to max flow. Here is your cheat sheet for both.

The Cheat Sheet

Coding Drill 1: Implement Edmonds-Karp

The most common interview ask. You need to code this from memory in 15 minutes. Here is the minimal, clean implementation:

python
from collections import deque, defaultdict

def max_flow(n, edges, s, t):
    """
    n: number of vertices (0-indexed)
    edges: list of (u, v, capacity)
    Returns: maximum flow value
    """
    cap = [[0] * n for _ in range(n)]
    adj = [[] for _ in range(n)]
    for u, v, c in edges:
        cap[u][v] += c
        adj[u].append(v)
        adj[v].append(u)  # for residual

    flow = [[0] * n for _ in range(n)]
    total = 0

    while True:
        # BFS
        par = [-1] * n
        par[s] = s
        q = deque([s])
        while q and par[t] == -1:
            u = q.popleft()
            for v in adj[u]:
                if par[v] == -1 and cap[u][v] - flow[u][v] > 0:
                    par[v] = u
                    q.append(v)
        if par[t] == -1: break

        # Find bottleneck
        b = float('inf')
        v = t
        while v != s:
            u = par[v]
            b = min(b, cap[u][v] - flow[u][v])
            v = u

        # Augment
        v = t
        while v != s:
            u = par[v]
            flow[u][v] += b
            flow[v][u] -= b
            v = u
        total += b

    return total

Coding Drill 2: Bipartite Matching via Max Flow

Given adjacency list of a bipartite graph, find maximum matching. The trick: vertex numbering. Left vertices = 0..L-1, right = L..L+R-1, source = L+R, sink = L+R+1.

python
def max_matching(L, R, edges):
    """L, R: number of left/right vertices. edges: list of (l, r)."""
    n = L + R + 2
    s, t = L + R, L + R + 1
    flow_edges = []
    for i in range(L):
        flow_edges.append((s, i, 1))  # source to left
    for j in range(R):
        flow_edges.append((L + j, t, 1))  # right to sink
    for l, r in edges:
        flow_edges.append((l, L + r, 1))  # left to right
    return max_flow(n, flow_edges, s, t)

LeetCode Patterns

Common Interview Mistakes

Chapter 9: Connections

Maximum flow sits at the crossroads of graph algorithms, optimization, and combinatorics. Here is how it connects to everything else you have studied.

Where Max Flow Fits

The Hierarchy of Flow Algorithms

Beyond CLRS

The maximum flow problem continues to inspire cutting-edge research. In 2022, Chen et al. achieved an almost-linear-time algorithm for max flow: O(E^1+o(1)). This was a breakthrough in theoretical CS, settling a decades-old question about the optimal complexity of max flow. The algorithm uses interior-point methods from continuous optimization combined with graph decomposition — a beautiful marriage of discrete and continuous math.

Related Lessons

Continue your graph algorithms journey:

"What I cannot create, I do not understand." — Richard Feynman