Back to the on-screen lesson ·
Integrality for free, total unimodularity, max-flow min-cut, and how fragile easiness is.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to write a network flow model with conservation at every node, compute the capacity of a cut and use it as a proof that a flow is maximum, and say why a totally unimodular constraint matrix makes integrality free. You will also be able to classify the standard discrete problems as easy or hard on the right grounds — the structure of the matrix rather than the number of solutions — and explain why a single side constraint can move a problem across that line.
From lesson 5: integrality is what makes a problem hard. From lesson 22: some relaxations come back integral on their own. This lesson says which ones, and why — and the answer is a property of the constraint matrix rather than of the data or the size.
A network flow model has a node per place and an edge per link. Flow $x_e \ge 0$ on each edge, capacity $x_e \le u_e$, and conservation at every node that is neither source nor sink:
$$\sum_{e \text{ into } v} x_e = \sum_{e \text{ out of } v} x_e.$$
Write that as a matrix and something unusual happens: each column (one per edge) has exactly one $+1$ and one $-1$, and zeros elsewhere. Such a matrix is totally unimodular — every square submatrix has determinant $0$, $1$ or $-1$.
Why that matters. A vertex of $\{x : Ax = b,\ x \ge 0\}$ is found by solving a square subsystem, and Cramer's rule divides by that subsystem's determinant. If the determinant is $\pm 1$ and $b$ is integral, the vertex is integral. So every vertex of the relaxation is a whole-number point, and a simplex method — which stops at a vertex — returns integers without being asked.
The integrality constraint was never a restriction. There is no integrality gap, no branching, no search: the linear program is the integer program.
| Problem | Easy? | Why |
|---|---|---|
| Shortest path (non-negative weights) | yes | flow structure |
| Assignment | yes | flow structure |
| Maximum flow | yes | flow structure |
| Minimum-cost flow | yes | flow structure |
| Travelling salesman | no | subtour constraints break it |
| Knapsack | no | the capacity row breaks it |
Max-flow min-cut. The maximum flow from source to sink equals the minimum capacity of a cut separating them. A cut is a certificate: every flow must cross it, so no flow exceeds its capacity, and finding a cut whose capacity equals your flow proves the flow optimal. It is lesson 13's duality, in a combinatorial costume.
And it is fragile. Add one row that does not have the flow structure — at most $k$ toll roads, a budget across edges — and total unimodularity is gone. The problem looks almost identical and is NP-hard.
Another way: picture
A network of pipes with a tap at one end and a drain at the other. Every junction passes on exactly what it receives. Now imagine slicing through the network so the tap is on one side and the drain on the other: the total width of the pipes you cut is a ceiling on the flow, and the narrowest place you could have sliced is the flow.
Another way: steps
To tell whether a discrete problem is easy:
Match $n$ workers to $n$ jobs, one each, at least total cost. There are $n!$ matchings — for $n = 20$, more than a billion billion — so it looks like a combinatorial explosion.
It is not. Write $x_{ij} \in \{0,1\}$ for worker $i$ on job $j$, with $\sum_j x_{ij} = 1$ for each worker and $\sum_i x_{ij} = 1$ for each job. That matrix is the incidence matrix of a bipartite graph, which is totally unimodular. So the relaxation's vertices are integral, the linear program returns a genuine matching, and $n = 20$ is trivial.
The lesson is that the number of feasible solutions is not what makes a problem hard. Linear programming also has infinitely many feasible points and is easy. What decides it is the shape of the feasible region — whether the corners the method lands on are the answers you can use.
Assuming discrete means hard. Half the classic combinatorial problems are polynomial. Check the structure before reaching for branch and bound.
Assuming a network model stays easy. One side constraint on a subset of edges can lose it. The core being a flow problem is not enough.
Counting solutions as evidence. $n!$ matchings and the problem is easy; $2^n$ knapsacks and it is hard. The count predicts nothing.
Forgetting integral data. Total unimodularity gives integral vertices only when the right-hand side is integral. Fractional capacities give fractional vertices, and the guarantee is gone.
Two problems about the same network, with the same data, can sit on opposite sides of the polynomial line depending on which constraints are written. That is uncomfortable — it means "is this problem hard" cannot be answered from a description in words, only from the matrix — and it is also useful. When a model turns out to be intractable, the first question is not "is the problem inherently hard" but "is there a formulation of it that keeps the flow structure", and often there is: reformulating a scheduling or routing model so that its core is a flow problem with as few non-flow side constraints as possible is standard practice, and it is worth more than any amount of solver tuning.
A network has a flow of $7$ from source to sink. Is it the maximum?
A flow, with no claim attached.
Find a cut: edges crossing forwards with capacities $4$ and $3$, so capacity $7$. Every unit of flow must cross this cut, so no flow exceeds $7$.
A bound from the other side.
The flow achieves $7$ and nothing can exceed $7$. So it is maximum — proved, by exhibiting the cut. That is a duality certificate of exactly lesson 13's kind, and in this setting the gap always closes, which is what max-flow min-cut asserts.
Flow and cut meet.
Shortest path from A to B in a graph with non-negative weights: a flow problem, totally unimodular, solved by Dijkstra in near-linear time.
Easy.
Add: the path may use at most three toll roads. The new row has a $1$ in each toll-road column and $0$ elsewhere — not the flow pattern.
One row of a different shape.
Total unimodularity is lost, the relaxation can return a fractional mixture of paths, and the problem is NP-hard. It is called the resource-constrained shortest path, and it is worth remembering precisely because the change looks so small: nothing about the graph changed, and the problem moved across the line.
Hard, from one innocuous requirement.
Ship from three factories to four customers at least cost, whole units only, with supplies and demands as whole numbers. Constraints: one per factory, one per customer.
Write down what the matrix looks like.
Each variable $x_{ij}$ appears in exactly two constraints — its factory's and its customer's — with coefficient $1$ in each. That is the bipartite incidence pattern, which is totally unimodular.
So yes: solve the linear program and the answer comes back in whole units, with no branching. And note the condition that was quietly used — supplies and demands are whole numbers. Make one of them $7.5$ and the vertices need not be integral any more, and the whole-unit requirement becomes a real restriction again.
Is the shortest path in a graph with non-negative weights solvable in polynomial time?
A node receives $6$ on one edge and $8$ on another, and sends $5$ out on a third. How much must leave on the last outgoing edge?
Answer:
A cut separating source from sink is crossed forwards by two edges of capacity $5$ and $5$, and backwards by one of capacity $4$. What is the cut's capacity?
Answer:
A network flow model with $8$ nodes and integer capacities is solved as a linear program, with no integrality requirement. Every variable comes back a whole number. Why?
Is assigning $n$ workers to $n$ jobs at least total cost solvable in polynomial time?
A shortest-path model has one constraint added: the path may use at most $6$ toll roads. What happens?
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
A node receives $6$ on one edge and $4$ on another, and sends $5$ out on a third. How much must leave on the last outgoing edge?
Answer:
You can recognise a flow problem, use a cut as a certificate, and say why total unimodularity makes integrality free. Next: what to do when none of this applies.
9. Your turn: is this transport problem easy?, step 3