Min-Cost Flow Interview Questions: Assignment, Residual Edges, and Negative Costs

Min-cost flow interview questions become difficult when a locally cheap assignment blocks a better complete solution. A strong answer explains how a residual graph repairs that decision, how much flow the problem requires, and why a negative residual edge does not automatically make the model invalid.

The central idea is reversible allocation. Sending flow changes the choices available next. A reverse edge records permission to cancel an earlier choice at its original cost; it does not describe a truck traveling backward or a worker earning negative pay.

Evidence boundary: Google OR-Tools documents supply, capacity, and assignment models. Boost documents a particular successive-shortest-path implementation and its input requirements. The traces, counterexamples, and preparation advice below are original exercises. They are not candidate reports or claims about a company's interview format.

For practice, use Minimize Total Assignment Distance and explain the model before selecting an algorithm. That habit exposes mistakes which a working shortest-path routine cannot fix.

What problem does min-cost flow actually solve?

For each directed edge, choose flow between zero and its capacity. Respect the balance required at every vertex and minimize the sum of edge flow times unit cost. OR-Tools' min-cost-flow documentation uses positive supply for net outgoing flow and negative supply for net incoming flow. Declare that sign convention rather than expecting an interviewer to infer it.

Three objectives often get conflated. Sending exactly F units asks for the cheapest feasible flow of that size. Min-cost maximum flow first seeks maximum feasible flow and then minimizes cost among those flows. A supply-demand model specifies balances directly. They can describe equivalent instances, but an implementation must return the right contract.

If only one of two required assignments is possible, returning its low cost as a successful answer is wrong. Report infeasibility or explicitly return both achieved flow and cost. If optional work is permitted, encode that choice and its penalty. Do not accidentally make every task optional because stopping augmentation early looks economical.

Ask whether costs are per unit, whether capacities are integral, and whether there are lower bounds. A capacity of three does not mean three separate fixed fees. A setup cost paid once for opening a route usually needs a different model. Negative costs may represent benefits, but their meaning and bounds must remain explicit.

How do you turn assignment into a network?

Create a source, one vertex per worker, one vertex per task, and a sink. Source-to-worker capacity one limits each worker to one assignment. Worker-to-task edges exist only for allowed pairs and carry the assignment cost. Task-to-sink capacity one limits each task to one worker. Request the required number of assignments.

This matches the structure in OR-Tools' assignment example. The original interview exercise here uses two workers and two tasks:

Worker	Task X	Task Y
A	1	2
B	2	100

Greedily assigning A to X costs one. B then appears forced into Y, giving total 101. The optimal complete assignment is A to Y and B to X, total four. A useful answer must show how the algorithm reaches four after initially choosing the cheapest edge.

Missing permissions should normally mean missing edges. A giant numerical cost for a forbidden pair can accidentally produce an invalid assignment when no legal solution exists. It can also overflow accumulated costs. If penalties are intentional, explain what paying one means in the business problem.

Additional capacity layers can represent some quotas. Arbitrary rules such as “these two specific assignments may never coexist” are not automatically ordinary network capacities. Identify which constraints remain representable and when a different optimization formulation is needed.

Trace the reverse edge that repairs the first choice

After one unit follows source → A → X → sink, the residual graph includes X → A with capacity one and cost minus one. The forward A → X edge has no remaining capacity. The next augmenting path can be:

source → B → X → A → Y → sink
             2   -1    2
path cost = 3

The path adds B–X, cancels A–X, and adds A–Y. The first augmentation cost one; the second changes the objective by three. Final cost is four. The source and sink edges have zero cost in this example.

This is the crucial interpretation: X → A is an accounting operation that undoes one unit of A → X. It releases the earlier allocation while preserving flow conservation. Describe the resulting assignments, not just a path containing a negative number.

For an original edge of capacity C, cost c, and current flow x, residual forward capacity is C−x and residual reverse capacity is x. Their costs are c and −c. Augmenting by delta subtracts delta from the chosen residual edge's capacity and adds it to its paired reverse edge.

Real networks may also contain an original edge in the opposite direction. That edge and the synthetic reverse edge are separate objects. Store reverse-edge indices, not a lookup by endpoint pair, or parallel edges can overwrite one another. Updating the wrong reverse edge can return a plausible cost while violating the final allocation.

Why can't ordinary Dijkstra handle every residual graph?

Dijkstra's usual correctness argument requires nonnegative edge weights. Residual reverse edges can have negative costs even when every original assignment cost is nonnegative. Running ordinary Dijkstra directly on those costs invalidates that argument.

One approach uses vertex potentials p and reduced costs:

reduced(u,v) = cost(u,v) + p[u] - p[v]

When feasible potentials make all relevant residual reduced costs nonnegative, Dijkstra can run on the reduced costs. After obtaining distances d, update reached vertices with p[v] += d[v]. Keep unreachable vertices out of that update; adding an infinity sentinel is not a meaningful potential.

Reduced path costs differ from original path costs by a telescoping endpoint term. Using the old potentials, original path cost equals reduced distance to the sink minus p[source] plus p[sink]. Alternatively, sum the original edge costs along the recovered path. Mixing old and updated potentials in the conversion can yield a correct route with an incorrect objective.

For a tiny original example, let A → X have cost −3, p[A]=0, and p[X]=−3. Its reduced cost is zero. After flow is sent, X → A has original cost three and reduced cost 3−3−0=0. A negative original cost and a nonnegative reduced cost are entirely compatible.

This arithmetic is an illustration, not permission to choose arbitrary potentials for a whole graph. Check every usable residual edge. If initial negative edges exist and no relevant negative cycle prevents shortest paths, a shortest-path initialization such as Bellman–Ford can establish suitable distances. The initialization and algorithm assumptions belong in the answer.

Does a negative cycle mean the answer is unbounded?

Not necessarily. A negative cycle permits reducing cost by circulating flow around it, but finite capacities bound how much can circulate. A cycle whose usable capacity is two can offer a limited improvement. Unbounded cost reduction requires an appropriate unbounded feasible direction, such as unlimited capacity around a negative-cost cycle.

A simple shortest-augmenting-path implementation may still be unable to handle that finite negative cycle correctly. “The optimum is bounded” and “my algorithm supports the instance” are different claims. Explain whether the chosen library rejects such inputs, whether its formulation avoids them, or whether a more general method is required.

Boost's nonnegative-weights successive-shortest-path API documents a specific representation: forward edges have nonnegative weights, and paired reverse edges have negated weights and initially zero capacity. That requirement should not be generalized to every min-cost-flow algorithm.

An interview answer improves when it separates mathematical feasibility, boundedness, and implementation support. A solver status is part of the result. Never reinterpret an unsupported or infeasible status as cost zero.

What makes the implementation reliable under pressure?

Maintain explicit invariants. Every augmentation uses edges with positive residual capacity. Delta is no greater than the path bottleneck or the remaining requested flow. Each edge and its reverse agree on their pairing. Final flow respects original capacities and every vertex balance.

Use a numeric type that holds the largest possible total cost, not just one edge's cost. Multiplying a large augmentation by a large unit cost can overflow before adding it to the accumulator. If your language permits silent overflow, test the product boundary as well as the sum.

For integral capacities, augmenting by the bottleneck sends integral flow. Sending one unit at a time can be unnecessarily slow when a path permits many units. Conversely, stating a complexity bound without naming the number of augmentations hides an important dependency. With heap-based Dijkstra, a typical bound has the form number of augmentations times the shortest-path work, plus initialization; capacities and the network structure determine that count.

For small assignment instances, enumerate all legal permutations and compare their best cost against your flow implementation. Include the two-by-two rerouting trap, negative assignment costs without initial cycles, missing pairs, unequal partition sizes, and an impossible required flow. Inspect the final chosen pairs, not only the cost.

Then test structural failures: parallel edges with different costs, zero-capacity edges, disconnected vertices, and a path whose bottleneck exceeds one. Those cases reveal pairing and balance defects that random positive-cost matrices may miss.

A final reconciliation check recomputes cost from the chosen original edges and compares it with the accumulated augmentation cost. It also counts completed assignments and checks each worker and task limit independently. Agreement on the objective alone can conceal a flow-balance defect, so verify the allocation and its arithmetic together.

Practice the model, trace, and result contract

In a timed answer, first state the required flow and network construction. Next explain the residual replacement using the four-cost matrix. Only then discuss potentials and performance. This ordering lets the interviewer see what the algorithm is optimizing before hearing its machinery.

A useful self-check is to ask: what earlier decision could this path undo, and what final allocation does it produce? If you cannot answer that in ordinary language, the residual trace needs another pass.

Practice question	What to explain
Minimize Total Assignment Distance	Translate pair costs into a complete assignment contract.
Count Distinct Hat Assignments and Maximize Hat Points	Decide whether counting and optimization need different models.
Assign 2n Workers to Two Tasks to Minimize Total Time	Compare capacity constraints with a specialized assignment solution.
Find Shortest Paths in Road Network	Explain why residual costs change shortest-path assumptions.
Find the Most Reliable Path Through a Network	Compare multiplicative reliability with additive cost.

Start with Minimize Total Assignment Distance and write your assumptions before answering. Compare your explanation against the specific invariants above, then use a second question to test whether the reasoning transfers to a different constraint.

Sources and Further Reading

• OR-Tools min-cost flow
• OR-Tools assignment using min-cost flow
• Boost successive shortest path with nonnegative weights