Maximum Flow and Minimum Cut (Intro)

This is an extension topic beyond most interviews; it pays off in top-tier rounds and hard OAs that hide an assignment, disjoint-paths or "cheapest way to separate" question behind the story.

Intuition

A flow network is a directed graph with a capacity on every edge, a source s and a sink t. A flow assigns each edge an amount between 0 and its capacity, and every vertex other than s and t passes on exactly what it receives. The maximum flow is the largest total amount that can leave s.

Greedily pushing flow along any s -> t path gets stuck in local optima. The fix is the residual graph: when you push x units along u -> v, you also create x units of capacity on a reverse edge v -> u. Using that reverse edge later means "take back some of that flow and reroute it". Now the rule is simple (Ford-Fulkerson): while the residual graph has an s -> t path (an augmenting path), push its bottleneck capacity along it.

Why does this stop at the optimum? An s-t cut splits the vertices into a side S containing s and a side T containing t; its capacity is the total capacity of edges going from S to T. Every unit of flow must cross every cut, so any flow is at most any cut. When no augmenting path remains, let S be the vertices still reachable from s in the residual graph: every edge from S to T is saturated and every edge from T back to S is empty, so the flow equals the capacity of that cut. That is the max-flow min-cut theorem: the maximum flow equals the minimum cut, and the final residual graph hands you the cut for free.

Edmonds-Karp picks each augmenting path with BFS (fewest edges), which bounds the number of augmentations by O(V * E). Dinic's algorithm augments along many shortest paths per BFS phase and is the faster standard choice for larger graphs.

When to use it in interviews / OAs

• Assignment with capacities: workers to jobs, students to courses with seat limits, each item used at most k times.
• Maximum number of edge-disjoint or vertex-disjoint routes between two nodes.
• "Minimum total cost of edges (or vertices) to remove so that A cannot reach B": a min cut.
• "Pick projects with profits, some require costly prerequisites; maximize profit": project selection (maximum weight closure).
• Two-way choices with pairwise penalties (each item goes to group A or B, and separating some pairs costs extra): min cut with s = A and t = B.

Template

Edmonds-Karp with residual edges

Edges are stored in pairs: edge i and its reverse i ^ 1.

from collections import deque


class MaxFlow:
    def __init__(self, n: int):
        self.n = n
        self.adj: list[list[int]] = [[] for _ in range(n)]  # edge ids leaving each vertex
        self.to: list[int] = []
        self.cap: list[int] = []  # residual capacity

    def add_edge(self, u: int, v: int, c: int) -> None:
        self.adj[u].append(len(self.to))
        self.to.append(v)
        self.cap.append(c)
        self.adj[v].append(len(self.to))  # reverse edge starts empty
        self.to.append(u)
        self.cap.append(0)

    def max_flow(self, s: int, t: int) -> int:
        flow = 0
        while True:
            prev = [-1] * self.n  # edge used to reach each vertex in this BFS
            prev[s] = -2
            q = deque([s])
            while q and prev[t] == -1:
                u = q.popleft()
                for e in self.adj[u]:
                    v = self.to[e]
                    if self.cap[e] > 0 and prev[v] == -1:
                        prev[v] = e
                        q.append(v)
            if prev[t] == -1:
                return flow  # no augmenting path: the flow is maximum
            push, v = float("inf"), t
            while v != s:  # bottleneck of the path
                push = min(push, self.cap[prev[v]])
                v = self.to[prev[v] ^ 1]
            v = t
            while v != s:
                e = prev[v]
                self.cap[e] -= push
                self.cap[e ^ 1] += push  # lets a later path undo this flow
                v = self.to[e ^ 1]
            flow += push

    def source_side(self, s: int) -> list[bool]:
        # after max_flow: True for vertices on the s side of a minimum cut
        seen = [False] * self.n
        seen[s] = True
        stack = [s]
        while stack:
            u = stack.pop()
            for e in self.adj[u]:
                if self.cap[e] > 0 and not seen[self.to[e]]:
                    seen[self.to[e]] = True
                    stack.append(self.to[e])
        return seen

The cut edges are the original edges u -> v with u on the source side and v not.

Modeling 1: project selection (maximum weight closure)

Choosing item a forces choosing item b for every rule (a, b); profits may be negative. Connect s -> i with capacity profit for positive items, i -> t with capacity -profit for negative ones, and a -> b with infinite capacity. Cutting s -> i means "skip a profitable item"; cutting i -> t means "pay for a costly item".

def max_profit_closure(profit: list[int], requires: list[tuple[int, int]]) -> int:
    n = len(profit)
    s, t = n, n + 1
    mf = MaxFlow(n + 2)
    big = sum(abs(p) for p in profit) + 1  # effectively infinite
    for i, p in enumerate(profit):
        if p > 0:
            mf.add_edge(s, i, p)
        elif p < 0:
            mf.add_edge(i, t, -p)
    for a, b in requires:
        mf.add_edge(a, b, big)
    return sum(p for p in profit if p > 0) - mf.max_flow(s, t)

Modeling 2: vertex-disjoint paths by node splitting

A vertex capacity becomes an edge capacity if every vertex v is split into v_in -> v_out. Here every inner vertex may be used by one path.

def max_vertex_disjoint_paths(n: int, edges: list[tuple[int, int]], s: int, t: int) -> int:
    mf = MaxFlow(2 * n)  # v_in = v, v_out = v + n
    for v in range(n):
        mf.add_edge(v, v + n, n if v in (s, t) else 1)
    for u, v in edges:
        mf.add_edge(u + n, v, 1)  # u_out -> v_in
    return mf.max_flow(s, t + n)

Complexity

Edmonds-Karp runs in O(V * E^2) time in the worst case and O(V + E) memory; on interview-sized graphs it is far faster than the bound. Dinic's algorithm is O(V^2 * E) in general and O(E * sqrt(V)) on unit-capacity bipartite networks. Recovering the min cut after the flow is one extra traversal, O(V + E).

Common pitfalls

• No reverse edges. Without them, the greedy can lock in a bad path and return less than the maximum.
• Undirected edges. Add capacity in both directions (two edges, or one edge whose reverse also gets capacity c).
• "Infinite" capacities must exceed any possible finite cut; the sum of all finite capacities plus one is safe.
• Reading the cut before running the flow, or from the original graph instead of the residual one.
• DFS augmenting with huge capacities. Plain Ford-Fulkerson with arbitrary paths can take as many iterations as the flow value; BFS (Edmonds-Karp) or Dinic avoids that.
• Several sources or sinks. Add a super source with edges to every source (and a super sink), with capacities equal to each supply or demand.

Interview variations

• Bipartite matching is max flow on a unit network (s -> left -> right -> t); a direct augmenting-path matcher is shorter.
• Edge-disjoint paths. Give every edge capacity 1; the max flow is the number of paths (and, by Menger's theorem, the minimum number of edges whose removal separates s from t).
• Vertex-disjoint paths and vertex costs. Node splitting as above; use the vertex's cost as the split edge capacity for "cheapest set of nodes to remove".
• Project selection, image segmentation, two-group partition with penalties. All are min cuts on a cleverly built network.
• Capacitated assignment. Worker i can take up to k_i jobs: capacity k_i on s -> worker_i.
• Min-cost flow (cheapest maximum flow) and flows with lower bounds are beyond interview scope.