Network Flow Concepts — Max Flow, Min Cut, and Edmonds-Karp [Ford-Fulkerson, Google, Amazon]

Algorithm Statement#

Max flow problem: Given a directed graph with non-negative edge capacities cap[u][v], a source vertex s, and a sink vertex t, find the maximum amount of flow that can be pushed from s to t such that:

1. Capacity constraint: for every edge, 0 <= flow[u][v] <= cap[u][v].
2. Conservation: for every vertex v other than s and t, total flow in equals total flow out.

The answer equals the minimum cut capacity by the Max-Flow Min-Cut Theorem (Ford-Fulkerson, 1956).

Constraints (typical FAANG):

• 2 <= V <= 500
• 0 <= E <= 10^4
• 0 <= cap <= 10^9
• Integer or rational capacities (irrational capacities can cause Ford-Fulkerson non-termination).

Example 1:

Network: s -> a (cap 3), s -> b (cap 2), a -> t (cap 2), b -> t (cap 3),
         a -> b (cap 1).
Max flow s -> t = 5.
Min cut = {(s, a), (s, b)} with total capacity 5.

Example 2:

Bipartite matching reduction: 4 jobs, 4 workers, each worker qualified for some
jobs. Add super-source -> each worker (cap 1), each job -> super-sink (cap 1),
worker -> job (cap 1) for every qualification. Max flow = max matching.

Why This Problem Matters#

Network flow is the deepest single algorithm topic in FAANG senior interviews. Google, Amazon, and Meta ask flow-flavoured questions in disguise: bipartite matching, project selection with profit constraints, image segmentation, baseball elimination, multi-source multi-sink routing, capacity planning for distributed systems. The questions almost never say "max flow" out loud — recognising the reduction is the entire game.

Modelling intuition that flow problems exercise:

• Bipartite matching — Hall's theorem and Konig's theorem both reduce to min cut.
• Project selection / closure — pick a subset to maximise profit subject to dependencies, by solving min cut.
• Edge-disjoint paths — set every capacity to 1; max flow = number of edge-disjoint paths.
• Vertex-disjoint paths — node-splitting trick: replace each vertex with two copies connected by a unit-capacity edge.
• Multi-source multi-sink — add a super-source and super-sink with infinite-capacity edges.

The interview value is twofold. First, fluency with the Ford-Fulkerson template (BFS-driven Edmonds-Karp) shows you can code residual graphs without bugs. Second, the modelling skill to recognise and reduce arbitrary problems to max-flow is one of the highest-value algorithmic muscles a senior engineer can demonstrate.

The Core Insight#

A residual graph Gf for a flow f adds:

• A forward edge u -> v with capacity cap[u][v] - flow[u][v] (remaining capacity).
• A backward edge v -> u with capacity flow[u][v] (the amount of flow we could "undo").

An augmenting path is any path from s to t in Gf with positive residual capacity. We push flow equal to the bottleneck capacity along that path, updating both forward and backward residuals.

Ford-Fulkerson keeps finding augmenting paths until none exist; the resulting flow is maximum. The proof uses the Max-Flow Min-Cut Theorem:

max flow value = min cut capacity

A cut (S, T) partitions vertices with s in S and t in T. Its capacity is the total capacity of edges from S to T. The minimum such cut equals the maximum flow — so once we know one we know the other.

Edmonds-Karp specialises Ford-Fulkerson by always picking a shortest augmenting path (BFS by edge count). This guarantees O(V * E^2) time independent of capacities, while a naive DFS picker can be exponential or even non-terminating on irrational capacities.

For dense graphs and large capacities, Dinic's algorithm runs in O(V^2 * E) or O(E * sqrt(V)) for unit-capacity graphs (perfect for bipartite matching). For very large graphs, push-relabel runs in O(V^2 * sqrt(E)).

Visual Dry Run#

Network: s -> a (cap 3), s -> b (cap 2), a -> b (cap 1), a -> t (cap 2), b -> t (cap 3).

Iteration 1 (BFS-shortest augmenting path): s -> a -> t, bottleneck = 2.

• Push 2. Flow now s-a = 2, a-t = 2.

Iteration 2: s -> a -> b -> t, bottleneck = min(3-2, 1, 3) = 1.

• Push 1. Flow now s-a = 3, a-b = 1, b-t = 1.

Iteration 3: s -> b -> t, bottleneck = min(2, 3-1) = 2.

• Push 2. Flow now s-b = 2, b-t = 3.

Iteration 4: BFS finds no s -> t path in residual graph. Stop.

Total flow = 2 + 1 + 2 = 5. Min cut = {(s,a), (s,b)}, capacity 3 + 2 = 5.

Solution (Optimal)#

Python — Edmonds-Karp O(V * E^2)#

from collections import deque
 
def edmonds_karp(n, cap, s, t):
    """cap is a V x V matrix of capacities; mutated in place into residual."""
    flow = 0
 
    def bfs(parent):
        parent[s] = s
        q = deque([s])
        while q:
            u = q.popleft()
            for v in range(n):
                if parent[v] == -1 and cap[u][v] > 0:
                    parent[v] = u
                    if v == t:
                        return True
                    q.append(v)
        return False
 
    while True:
        parent = [-1] * n
        if not bfs(parent):
            break
        # bottleneck along the augmenting path
        bottleneck = float('inf')
        v = t
        while v != s:
            u = parent[v]
            bottleneck = min(bottleneck, cap[u][v])
            v = u
        # update residuals
        v = t
        while v != s:
            u = parent[v]
            cap[u][v] -= bottleneck
            cap[v][u] += bottleneck
            v = u
        flow += bottleneck
    return flow

JavaScript — Edmonds-Karp#

function edmondsKarp(n, cap, s, t) {
    let flow = 0;
    while (true) {
        const parent = new Array(n).fill(-1);
        parent[s] = s;
        const q = [s];
        let found = false;
        while (q.length && !found) {
            const u = q.shift();
            for (let v = 0; v < n; v++) {
                if (parent[v] === -1 && cap[u][v] > 0) {
                    parent[v] = u;
                    if (v === t) { found = true; break; }
                    q.push(v);
                }
            }
        }
        if (!found) break;
        let bn = Infinity;
        for (let v = t; v !== s; v = parent[v]) {
            bn = Math.min(bn, cap[parent[v]][v]);
        }
        for (let v = t; v !== s; v = parent[v]) {
            cap[parent[v]][v] -= bn;
            cap[v][parent[v]] += bn;
        }
        flow += bn;
    }
    return flow;
}

Complexity#

For typical interviews with V <= 500 and integer capacities, Edmonds-Karp is the right default.

Common Mistakes#

• Forgetting the backward residual edge. Without cap[v][u] += bn you cannot "undo" flow when a better routing appears later.
• Using DFS without capacity-scaled bottleneck control. On irrational capacities, naive DFS Ford-Fulkerson may not terminate.
• Not building both directions of the residual capacity matrix. Even if the input has only u -> v, the residual must allow v -> u for backward edges.
• Confusing flow and capacity. Maintain them separately or merge by treating cap as the residual matrix and the original cap as immutable.
• Forgetting to handle parallel edges. Either coalesce them (sum capacities) or use an adjacency-list representation with edge indices and a paired backward edge stored at index i ^ 1.

Interview Tips#

• Open with the modelling step, not the algorithm: "I claim this reduces to max flow with these capacities and this source-sink construction."
• State the Max-Flow Min-Cut Theorem out loud — it earns immediate credit and lets you describe min cut solutions interchangeably.
• Use the edge-list with twin index representation if your interviewer asks for production-quality code. Each edge has to, cap, and a paired index for O(1) residual updates.
• Mention Dinic's or push-relabel for dense graphs, and the Hopcroft-Karp specialisation for bipartite matching with O(E * sqrt(V)).
• For modelling-only questions (when implementation is not expected), spending five minutes on the reduction and two minutes on the algorithm choice is the right ratio.

Follow-up Questions#

• Bipartite matching? Add super-source connecting to one side and super-sink connecting from the other; all capacities 1. Max flow = max matching.
• Vertex capacities? Split each vertex v into v_in -> v_out with capacity equal to the vertex capacity; reroute edges accordingly.
• Multi-source multi-sink? Add a super-source connecting to all sources with infinite capacity; super-sink from all sinks similarly.
• Min-cost max-flow? Use SPFA / Bellman-Ford to find the cheapest augmenting path (negative-cycle-free residual graph).
• Project selection problem? Build a graph where source connects to profitable projects, unprofitable tasks connect to sink, and dependencies use infinite capacity; min cut yields the optimal selection.
• Edge-connectivity between two vertices? Set all capacities to 1 and run max flow; the answer is the edge-connectivity by Menger's theorem.

Key Takeaways#

• The Max-Flow Min-Cut Theorem links flow values to cut capacities — knowing one tells you the other.
• Ford-Fulkerson augments paths in the residual graph until none remain; Edmonds-Karp uses BFS to bound runtime at O(V * E^2).
• Maintain a residual graph with both forward and backward capacities; backward edges allow flow rerouting.
• Bipartite matching, project selection, vertex-disjoint paths, and image segmentation all reduce to max flow.
• Dinic's O(V^2 * E) and push-relabel O(V^2 * sqrt(E)) are faster for dense graphs; Hopcroft-Karp is O(E * sqrt(V)) for bipartite matching.
• Companies that ask this: Google, Amazon, Meta, Microsoft, Bloomberg, Stripe, Citadel, Two Sigma.