What Is a Flow Network? Max Flow, Min Cut, and Why It Matters

You've never heard of flow networks, and yet they've been quietly running your life. Your morning commute. Water through pipes. The internet packets getting this article to your screen right now. All of them answer the same question: how much stuff can you push from one end to the other without anything catching fire?

The math behind that question is surprisingly elegant. It's also the kind of thing that shows up in senior-level interviews when the interviewer is tired of asking binary tree questions.

The Setup: What a Flow Network Actually Is

A flow network is a directed graph where every edge has a capacity, the maximum amount of stuff that edge can carry at once. Two special nodes get names:

Source (s): where flow originates
Sink (t): where flow is collected

Flow moves from source to sink along edges, respecting two rules:

Capacity constraint: the flow on any edge cannot exceed that edge's capacity. If an edge has capacity 10, at most 10 units flow through it.
Conservation of flow: for every node that is not the source or sink, whatever flows in must flow out. No node hoards flow or conjures it from nowhere.

Here's a concrete example. Four nodes: S (source), A, B, T (sink).

Flow network example with four nodes S, A, B, T showing capacities on directed edges

Numbers on edges are capacities. You want to push as much flow as possible from S to T. You can route up to 10 through S→A→T and up to 8 through S→B→T, but the A→T edge limits the top path to 9 and the B→T edge limits the bottom to 7. The A→B edge lets you reroute overflow.

The maximum flow problem asks: what is the largest total flow you can route from S to T without violating any capacity?

The answer here is 15. Getting there, though, requires an insight that trips everyone up the first time.

The Residual Graph: The Key Idea Everyone Glosses Over

Most explanations jump straight to algorithms, and then the "backward edge" concept hits you like a riddle wrapped in graph theory. It isn't magic. It's ctrl-Z for routing decisions.

Suppose you've already routed 5 units through edge A→T (capacity 9). The residual graph tracks what's still possible:

Forward edge A→T: residual capacity = 9 - 5 = 4 (you can push 4 more)
Backward edge T→A: residual capacity = 5 (you can "cancel" up to 5 units of the previous routing decision)

The backward edge is not a real pipe going backward. It's an accounting trick that lets the algorithm undo a suboptimal routing decision. Without it, a greedy first-path choice could permanently block a better solution.

The residual graph is what makes iterative improvement possible. Every time you find a path from S to T in the residual graph (an "augmenting path"), you increase the total flow by the minimum residual capacity on that path, then update the residual capacities. Repeat until no augmenting path exists.

Picture it like rerouting a traffic jam: you don't add new roads, you just tell some cars "actually, you should have gone the other way."

The Max-Flow Min-Cut Theorem

A cut is any partition of the graph's nodes into two sets: one containing the source, one containing the sink. The capacity of the cut is the sum of capacities on edges crossing from the source side to the sink side.

Ford and Fulkerson proved in 1956:

Maximum flow = minimum cut capacity.

Why? The min cut is a bottleneck: every unit of flow from S to T must cross the cut, so max flow can never exceed min cut capacity. When the algorithm terminates (no augmenting path left), you can construct a cut whose capacity equals the current flow. Those two facts together prove equality.

This is the surprisingly useful part. Finding the maximum flow automatically finds the minimum cut, which answers a completely different-looking question: what edges must you remove to disconnect S from T? Same computation. Two free answers.

The Algorithms

Three algorithms dominate. You need to know all three names and their complexities.

Ford-Fulkerson

The foundational method. Find any augmenting path (DFS or BFS), push flow, update residuals, repeat.

Time complexity: O(E · F), where F is the maximum flow value.

The problem: Ford-Fulkerson is technically correct, which is the best kind of correct, until you hand it a graph with a 10⁹ capacity edge and watch your interview timer expire. With irrational capacities, it may not even terminate. At all. Forever. This is not a hypothetical.

Edmonds-Karp

Edmonds-Karp is Ford-Fulkerson with one change: always use BFS to find the shortest augmenting path (fewest edges).

Time complexity: O(V · E²).

That exponent looks worse, but it's polynomial regardless of capacity values. The BFS choice guarantees that the shortest augmenting path length never decreases across iterations, bounding the number of augmentations to O(VE). Each BFS costs O(E), giving O(VE²) total.

This is the algorithm you implement in an interview unless the problem signals something bigger. Polynomial bound, clean implementation, no embarrassing edge cases.

Dinic's Algorithm

Dinic uses BFS to build a level graph (a layered subgraph of shortest paths), then finds a blocking flow within that level graph before repeating. This batches multiple augmentations per BFS pass.

Time complexity: O(V² · E), or O(E · √V) on unit-capacity graphs.

Dinic's is significantly faster in practice and is the go-to for competitive programming. For unit-capacity graphs (bipartite matching, for example), the O(E√V) bound makes it very efficient. You probably don't need to implement it in an interview, but knowing it exists signals that you've actually studied this stuff.

Algorithm	Time Complexity	When to Use
Ford-Fulkerson	O(E · F)	Small capacities, conceptual understanding
Edmonds-Karp	O(V · E²)	Interview default, polynomial guarantee
Dinic's	O(V² · E)	Competitive programming, large networks

Space complexity for all three: O(V + E) for the residual graph.

The Bipartite Matching Connection

Bipartite matching asks: given two groups of nodes (say, workers and tasks), where edges indicate who can do what, find the maximum number of worker-task pairs you can assign without any person or task appearing twice. Basically: the world's most dignified staffing problem.

You can reduce this to max flow in three steps:

Add a source S connected to every worker (capacity 1).
Add a sink T connected from every task (capacity 1).
Give every worker-task edge capacity 1.

Run max flow. The resulting flow value equals the maximum matching. Because all capacities are 1, an integral flow (which is guaranteed by the Integral Flow Theorem) directly encodes a valid matching.

König's theorem follows as a corollary: in a bipartite graph, the size of the maximum matching equals the size of the minimum vertex cover. This emerges automatically from the max-flow min-cut theorem applied to the bipartite flow network. Two famous theorems. One algorithm. Very satisfying.

Interview Reality

Flow networks sit at the edge of standard interview prep. Honest accounting:

Where they show up: Google, Meta, and other top-tier companies occasionally ask flow network problems at senior or staff levels, particularly when the problem involves resource assignment, scheduling with conflicts, or network reliability. A LeetCode discussion on Google onsites confirms these appear in practice, but they are not the majority of interviews.

The more common pattern: you won't see a raw "implement Ford-Fulkerson" question. You'll see a problem that can be modeled as max flow: scheduling tasks to workers, finding edge-disjoint paths, determining whether a certain assignment is feasible. Recognizing that the problem is a flow network is the skill being tested. The implementation is almost secondary. Almost.

Problems where flow thinking helps:

Bipartite matching (worker-task, student-project, job-assignment)
Network reliability (min edges to disconnect two nodes = min cut = max flow)
Circulation problems (does a feasible schedule exist given supply and demand constraints?)
Image segmentation in ML system design discussions (min cut on pixel graphs)

Problems that look like flow but aren't: shortest path (Dijkstra), minimum spanning tree (Kruskal/Prim), and connectivity checks (union-find) do not require flow. The distinguishing signal is a question about maximizing throughput or minimizing a separating set.

Spotting a Flow Network Problem

Before you reach for Edmonds-Karp, check for these signals:

The problem involves routing units through a network with capacity limits.
It asks for the maximum number of non-overlapping paths.
It asks for the minimum number of edges or nodes to "cut" connectivity.
It involves matching two sets with constraints on how many can match to each item.
It asks whether a given assignment or schedule is feasible given supply and demand.

If you see two or more of these signals together, the problem is probably reducible to max flow. If you see all five, you might be in a very specific Google phone screen.

A Minimal Implementation (Python)

Edmonds-Karp in about 30 lines. The residual graph is stored as an adjacency list of [to, capacity, reverse_index] triples.

from collections import defaultdict, deque

def max_flow(graph, source, sink, n):
    def bfs():
        visited = [-1] * n
        visited[source] = source
        q = deque([source])
        while q:
            u = q.popleft()
            for v, cap, _ in graph[u]:
                if visited[v] == -1 and cap > 0:
                    visited[v] = u
                    if v == sink:
                        return visited
                    q.append(v)
        return None

    flow = 0
    while True:
        parent = bfs()
        if parent is None:
            break
        # Find bottleneck
        path_flow = float('inf')
        v = sink
        while v != source:
            u = parent[v]
            for edge in graph[u]:
                if edge[0] == v and edge[1] > 0:
                    path_flow = min(path_flow, edge[1])
                    break
            v = u
        # Update residuals
        v = sink
        while v != source:
            u = parent[v]
            for edge in graph[u]:
                if edge[0] == v and edge[1] > 0:
                    edge[1] -= path_flow
                    graph[v][edge[2]][1] += path_flow
                    break
            v = u
        flow += path_flow
    return flow

def add_edge(graph, u, v, cap):
    graph[u].append([v, cap, len(graph[v])])
    graph[v].append([u, 0, len(graph[u]) - 1])

The backward edge is initialized with capacity 0. Every time you push flow forward, you add that amount to the backward edge. This is the residual graph living inside a single data structure. The algorithm needs no separate representation.

The Short Version

Residual graph: backward edges let the algorithm undo bad routing decisions. Without them, a greedy first path permanently blocks better solutions.
Max-flow = min-cut: the same computation answers both "how much can flow?" and "where is the bottleneck?"
Edmonds-Karp is your interview default (O(VE²), polynomial regardless of capacity). Dinic's is the competitive programming standard (O(V²E)).
Bipartite matching reduces to max flow with unit-capacity edges. The most common interview application by far.

If you want to practice recognizing these patterns under pressure, SpaceComplexity runs voice-based mock interviews where the interviewer asks you to model and solve graph problems exactly like this one, then gives rubric-based feedback on how you communicated your reduction before you wrote a line of code.