Max-Flow & Min-Cut Interview Questions

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. What a max-flow question is actually testing

Nobody is asked to implement Dinic's algorithm from memory. Flow questions are modelling questions: the interviewer describes a situation in plain English, and the whole exercise is whether you notice that it is a network, draw the right one, and name the theorem that finishes it.

That is why these questions have a reputation for being unfair. A candidate who has memorised twenty tree problems can be sunk by "assign these five engineers to these five teams" because they never make the jump from a story about people to a graph with a source and a sink. The algorithm is the easy half and it is available in any library.

Four phrasings account for nearly everything you will be handed.

Everything below is worked on that one six-node network, or on a small variant of it, and every number was computed and then recomputed by a second method before it was printed.

2. The template, and the two methods that matter

Write Dinic once and keep it. It is about thirty lines, it is fast enough for anything an interview will produce, and it gives you the minimum cut for free.

from collections import deque

class Dinic:
    def __init__(self, n):
        self.n = n
        self.to, self.cap, self.adj = [], [], [[] for _ in range(n)]

    def add(self, u, v, c):
        self.adj[u].append(len(self.to)); self.to.append(v); self.cap.append(c)
        self.adj[v].append(len(self.to)); self.to.append(u); self.cap.append(0)

    def bfs(self, s, t):
        self.level = [-1] * self.n
        self.level[s] = 0
        q = deque([s])
        while q:
            u = q.popleft()
            for e in self.adj[u]:
                if self.cap[e] > 0 and self.level[self.to[e]] < 0:
                    self.level[self.to[e]] = self.level[u] + 1
                    q.append(self.to[e])
        return self.level[t] >= 0

    def dfs(self, u, t, f):
        if u == t:
            return f
        while self.it[u] < len(self.adj[u]):
            e = self.adj[u][self.it[u]]
            v = self.to[e]
            if self.cap[e] > 0 and self.level[v] == self.level[u] + 1:
                d = self.dfs(v, t, min(f, self.cap[e]))
                if d > 0:
                    self.cap[e] -= d
                    self.cap[e ^ 1] += d
                    return d
            self.it[u] += 1
        return 0

    def max_flow(self, s, t):
        flow = 0
        while self.bfs(s, t):
            self.it = [0] * self.n
            while True:
                f = self.dfs(s, t, float('inf'))
                if f == 0:
                    break
                flow += f
        return flow

Two details in there are worth being able to explain, because they are exactly what a good interviewer probes.

The first is the paired edges. Every forward edge is stored next to its reverse edge, so e ^ 1 flips between them. The reverse edge starts at capacity zero and grows as flow is pushed. It exists so the algorithm can undo a bad decision: sending flow backwards along it cancels flow that was sent forwards. Without it the greedy first path can trap you below the optimum, and this is the single most common thing a candidate cannot explain.

The second is self.it, the current-arc optimisation. Once an edge has been exhausted in this phase it is never examined again, which is what takes Dinic from quadratic to its stated bound. Deleting that one line still gives correct answers and destroys the complexity.

Run it on the network in the figure and the answer is 16. Edmonds-Karp on the same network also returns 16, which is the cheapest sanity check available: two different algorithms, one answer.

3. Maximum bipartite matching

This is the question you are most likely to be asked, usually dressed as scheduling. "Five engineers, five teams, each engineer can work on some of them, maximise the number of people placed."

The reduction is mechanical. Add a source with an edge of capacity 1 into each engineer, a sink with an edge of capacity 1 out of each team, and capacity-1 edges for every allowed pairing. Because the capacities are integers, max flow returns an integral solution, and an integral flow of value k is exactly a matching of size k: capacity 1 out of the source stops anyone being used twice.

def max_matching(left, right, can):
    n = len(left) + len(right) + 2
    s, t = 0, n - 1
    g = Dinic(n)
    for i in range(len(left)):
        g.add(s, 1 + i, 1)
    for j in range(len(right)):
        g.add(1 + len(left) + j, t, 1)
    for i, l in enumerate(left):
        for r in can[l]:
            g.add(1 + i, 1 + len(left) + right.index(r), 1)
    return g.max_flow(s, t)

On the instance in the figure the answer is 4, not 5. Ada, Ben, Cleo and Dan can only reach backend, data and infra between them, so three roles have to absorb four people and one of them goes unplaced. That is Hall's condition failing, and naming it is worth more than the code: a matching that places every left vertex exists if and only if every subset of the left side has at least as many neighbours as it has members. The tightest witness here is smaller still: Ada, Cleo and Dan between them reach only backend and data, three people chasing two roles. Hall's condition is about saturating one side, and it coincides with a perfect matching only when the two sides are the same size, as they happen to be here.

If the interviewer is looking for the fastest possible answer rather than the most reusable one, Hopcroft-Karp runs in O(E√V) by augmenting along many shortest paths at once. Say it exists, then use Dinic, which on unit-capacity graphs achieves the same bound anyway.

4. The cover hiding inside the matching

A good follow-up, and one that catches most candidates: "now tell me the smallest set of people and teams that touches every possible assignment."

That is a minimum vertex cover, which is NP-hard in general graphs. In a bipartite graph it is not, and König's theorem says it is exactly the size of the maximum matching. You do not need a second algorithm; you read the cover off the cut you already have. Run a search from the source in the residual graph, then take the left vertices it cannot reach plus the right vertices it can.

On this instance that gives Ben, Eve, backend and data, four vertices, and checking by hand confirms all nine edges are touched. The complement of a vertex cover is an independent set, so the largest independent set is 10 − 4 = 6. Three separate questions, one max-flow call.

5. The minimum cut: the edges, not just the number

"What is the cheapest set of links to sever so that no traffic reaches the data centre?" The value is the max flow, by the theorem. But interviewers ask which links, and that is a different, easier step that many candidates never learned.

After the flow is maximum, run one search from the source over edges that still have residual capacity. Let R be the set it reaches. The minimum cut is every original edge from R to its complement.

def min_cut(self, s):
    seen = [False] * self.n
    seen[s] = True
    q = deque([s])
    while q:
        u = q.popleft()
        for e in self.adj[u]:
            if self.cap[e] > 0 and not seen[self.to[e]]:
                seen[self.to[e]] = True
                q.append(self.to[e])
    return [(self.to[e ^ 1], self.to[e])
            for e in range(0, len(self.to), 2)
            if seen[self.to[e ^ 1]] and not seen[self.to[e]]]

On the worked network the reachable set is {S, A, B} and the cut is A→C at 7 plus B→D at 9, which sums to 16, the flow value. Brute force over all sixteen possible source-side subsets confirms no cheaper cut exists.

Two traps live here. Only count edges going from the reachable set to the unreachable one; edges pointing back are not in the cut. And the minimum cut is often not unique, so if you are asked for "the" cut, say that you are returning one of possibly several and that they all have the same value.

6. Disjoint paths, and Menger's theorem

"How many independent routes are there from the office to the data centre?" is a flow question with every capacity set to 1.

Set each capacity to 1 and the max flow counts edge-disjoint paths, because a unit of flow cannot share an edge with another unit. Menger's theorem then says that number equals the minimum number of edges whose removal disconnects the two vertices. Max-flow min-cut is the weighted generalisation of exactly that statement.

On the worked network with unit capacities the answer is 2, and one minimum cut is the two edges leaving the source, though six different pairs of edges achieve it. That is worth pointing out rather than hiding: with unit capacities the answer is often just a degree bound, and saying so shows you understand what the number means instead of only how to compute it.

If the question says vertex-disjoint instead, capacities on edges cannot express it, and you need the first modelling trick below. Here that also gives 2, and removing C and D really does leave T unreachable. One hypothesis is worth saying out loud: the vertex form of Menger's theorem requires the two endpoints to be non-adjacent, which they are here because there is no direct S to T edge.

7. Three modelling tricks that turn a story into a network

Almost every flow interview question is one of these transformations wrapped around the same solver.

A vertex has a capacity. "This router can handle 3 units." Capacities live on edges, so split the vertex: replace v with v_in and v_out joined by an edge of capacity 3, send every arc that arrived at v into v_in, and start every arc leaving v from v_out. Setting the internal capacity to 1 is how you count vertex-disjoint paths.

Many sources, many sinks. "Three warehouses supply two shops." Add a super source with infinite-capacity edges to every real source, and a super sink fed by every real sink. One solver call replaces the enumeration a candidate might otherwise start writing.

The edge is undirected. Add both directions at full capacity. It looks like it should allow double the traffic and it does not, because the residual bookkeeping cancels flow sent in opposite directions. Be ready to say that, because it is a natural objection and the answer is short.

The fourth case is the one that catches people: a lower bound. "Every driver must take at least two shifts" is not a capacity, and the standard solver cannot express it. It needs a feasible-circulation construction, and the useful interview move is to notice the word "must" out loud rather than to code the whole thing.

8. Project selection, or why a cut can choose a subset

This one feels like it should be dynamic programming and is not, which is what makes it a favourite.

"Each project earns a known profit. Each project needs certain machines. Each machine costs a fixed amount and is shared by whatever needs it. Choose the most profitable subset."

The trap is greed: taking every project with a positive profit, or sorting by profit per machine. Neither is correct, because machines are shared, so a project's real cost depends on which other projects you take.

The construction is short. Source to each project with capacity equal to its profit; each machine to the sink with capacity equal to its cost; project to machine with infinite capacity so that edge can never be cut. Then the answer is

maximum profit = (sum of all profits) − (minimum cut)

and the projects to take are the ones on the source side of the cut. The infinite edges are what force consistency: if you keep a project on the source side, its machines must be there too, or the cut would be infinite. That is the definition of a closed set, and this is the maximum closure problem.

On the instance in the figure the profits total 235, the minimum cut is 195, and the best achievable is 40, by taking alpha, beta and gamma and dropping delta. Delta earns 30 but is the only project needing fab, which costs 50, so adding it to the other three costs 20 more than it brings in. Brute force over all sixteen subsets agrees.

9. Baseball elimination

A classic, and unusual in that the naive answer is not merely slow, it is wrong.

Given the standings and the remaining fixtures, is a given team still able to finish first? The obvious check is whether its best possible total still beats every rival's current total. That catches the easy cases and misses the interesting ones, because rivals have to play each other and somebody must win those games.

Here is a table where the naive check says nothing is wrong:

The Ducks can reach 79, and no rival has 79 wins yet, so no individual comparison eliminates them. But among the remaining fixtures the Aces play the Bolts twice, the Aces play the Comets once, and the Bolts play the Comets three times. Six games among the three rivals, and every one of them hands somebody a win.

Build a network: a source into one node per remaining pair, carrying the number of games they still play; each pair node into both of its teams with infinite capacity; each team into the sink with capacity equal to how many more wins it can afford before passing the Ducks' best case of 79. The Ducks survive only if all six games can be absorbed, that is, only if the max flow saturates the source.

It does not. The flow is 5 against 6 games, so one game has nowhere to go, and the Ducks are eliminated. Enumerating all 2⁹ outcomes of every remaining game in the league confirms it: there is no scenario in which the Ducks finish first, and there is a scenario for each of the other three.

The deficit also tells you why: the saturated team edges name the group of rivals who between them must win more games than they can afford. Interviewers who know this problem always ask for that explanation.

10. Minimum path cover in a DAG

"What is the fewest number of workers needed to run all these tasks, if a worker can only move between tasks that follow one another?"

That is a minimum path cover: the fewest vertex-disjoint paths covering every vertex of a directed acyclic graph. It reduces to matching by a trick worth remembering. Split every vertex into an out-copy on the left and an in-copy on the right, put an edge in the bipartite graph for each edge of the DAG, and find a maximum matching. Then

minimum path cover = number of vertices − maximum matching

because every matched edge joins two path fragments and so removes one path from the count. On a six-vertex DAG with seven edges the maximum matching is 4, so the minimum path cover is 6 − 4 = 2, and exhaustive search over every subset of edges agrees.

One qualification matters and is often omitted: this counts vertex-disjoint paths. If the paths are allowed to share vertices, take the transitive closure of the DAG first and then run the same reduction.

11. When it is min-cost flow, not max flow

The most common follow-up in the whole topic: "now each assignment has a cost, and I want the cheapest way to place everybody."

Max flow cannot answer that. It maximises quantity and is indifferent between two solutions of the same size, so it will happily return the most expensive perfect matching. What you need is minimum-cost maximum flow: among all flows of maximum value, find the one of least total cost.

The change to the model is small. Every edge gains a cost per unit alongside its capacity, and the algorithm repeatedly augments along the cheapest path in the residual graph rather than the shortest or any path. Because residual edges carry negative cost, plain Dijkstra does not apply directly, so the standard implementations either use Bellman-Ford, giving the successive shortest path algorithm, or keep Johnson-style potentials so Dijkstra stays usable.

Three things are worth being able to say about it.

The special case has a name. A complete bipartite graph with a cost on every pairing and a requirement that everyone is matched is the assignment problem, and the Hungarian algorithm solves it in O(n³). If the interviewer's problem is exactly "n workers, n jobs, minimise total cost", naming the Hungarian algorithm is the expected answer.

Integrality still holds. With integer capacities the minimum-cost maximum flow can still be taken to be integral, which is what keeps the matching interpretation valid once costs are added.

The trap is maximising a different thing. "Maximise total value" and "maximise the number of assignments" are not the same objective, and a solution can be optimal for one and poor for the other. Ask which one is wanted before writing anything, because the interviewer is often deliberately ambiguous to see whether you notice.

A useful boundary to state: if there are no costs, use max flow; if there are costs but every unit must move, it is min-cost flow; if the costs are on the vertices rather than the pairings, you are probably back in closure territory from section 8.

12. The complexity answers

Have these ready, and be ready to say which one you would actually use.

The warning is worth stating precisely because it is a common follow-up. Ford-Fulkerson is the only one whose running time depends on the capacity values rather than the size of the graph. Each augmenting path adds at least 1 to the flow, so the loop runs at most maxflow times, and if the capacities are a billion that bound is a billion iterations on a graph with four vertices. Since a capacity of a billion is ten digits of input, the running time is exponential in the input size. Edmonds-Karp fixes this by always choosing a shortest augmenting path, which removes the dependence on capacities entirely.

Two more facts earn credit. Integrality: if every capacity is an integer, some maximum flow is integral, which is what licences the matching and disjoint-path reductions. And the reduction cost: when you build a network from a story, quote the complexity in terms of the network you built, not the original input. A bipartite matching on n people and m roles builds a graph with n + m + 2 vertices, and saying so is what shows you understand the transformation.

13. Mistakes that fail the interview

Forgetting the reverse edges. The most common fatal bug, and it does not crash, it just returns a number that is too small. If you cannot explain why an algorithm needs to be able to cancel its own earlier decisions, you have not understood the algorithm.

Reusing the solver object. Calling max_flow a second time on the same instance returns 0, because the residual graph is already saturated. This bites people who compute a flow, then want the value again for a printout, and conclude their code is broken. Build a fresh object, or cache the result.

Answering the value when asked for the set. "Which links would you cut?" is not answered by "16". Recover the reachable set and list the edges.

Reading a lower bound as a capacity. "At most three shifts" is a capacity. "At least two shifts" is not, and it needs a different construction. Listen for "must" and "at least".

Modelling vertex limits as edge limits. If the constraint is on a machine rather than a link, split the vertex. Candidates who skip this get an answer that is silently too large.

Quoting Ford-Fulkerson as the complexity. It is the one bound that can be exponential in the input size. Name Dinic and explain the difference.

Reaching for flow when the problem is not a flow problem. Max flow is the wrong tool for shortest paths, for spanning trees, and for anything where the answer is a single route rather than a shared quantity. If nothing is being split or shared, look at BFS, Dijkstra or union-find first. A candidate who reaches for the heaviest hammer in the box is telling the interviewer something.

Silent modelling. The reduction is the answer. Draw the network on the whiteboard, say "source into each engineer at capacity one, because nobody can take two jobs", and let the interviewer correct the model before you have written thirty lines against the wrong one.

15. References

The results behind these questions, in chronological order.

1. Menger, K. (1927). “Zur allgemeinen Kurventheorie.” Fundamenta Mathematicae, 10, 96–115.
2. König, D. (1931). “Gráfok és mátrixok.” Matematikai és Fizikai Lapok, 38, 116–119.
3. Hall, P. (1935). “On representatives of subsets.” Journal of the London Mathematical Society, 10(1), 26–30.
4. Ford, L. R. and Fulkerson, D. R. (1956). “Maximal flow through a network.” Canadian Journal of Mathematics, 8, 399–404.
5. Ford, L. R. and Fulkerson, D. R. (1962). Flows in Networks. Princeton University Press.
6. Schwartz, B. L. (1966). “Possible winners in partially completed tournaments.” SIAM Review, 8(3), 302–308.
7. Dinic, E. A. (1970). “Algorithm for solution of a problem of maximum flow in networks with power estimation.” Soviet Mathematics Doklady, 11, 1277–1280.
8. Edmonds, J. and Karp, R. M. (1972). “Theoretical improvements in algorithmic efficiency for network flow problems.” Journal of the ACM, 19(2), 248–264.
9. Hopcroft, J. E. and Karp, R. M. (1973). “An n^5/2 algorithm for maximum matchings in bipartite graphs.” SIAM Journal on Computing, 2(4), 225–231.
10. Picard, J.-C. (1976). “Maximal closure of a graph and applications to combinatorial problems.” Management Science, 22(11), 1268–1272.
11. Goldberg, A. V. and Tarjan, R. E. (1988). “A new approach to the maximum-flow problem.” Journal of the ACM, 35(4), 921–940.
12. Ahuja, R. K., Magnanti, T. L. and Orlin, J. B. (1993). Network Flows: Theory, Algorithms, and Applications. Prentice Hall.
13. Wayne, K. D. (2001). “A new property and a faster algorithm for baseball elimination.” SIAM Journal on Discrete Mathematics, 14(2), 223–229.
14. Kleinberg, J. and Tardos, É. (2005). Algorithm Design, chapter 7. Addison-Wesley.
15. Cormen, T. H., Leiserson, C. E., Rivest, R. L. and Stein, C. (2009). Introduction to Algorithms, 3rd edition, chapter 26. MIT Press.