Minimum Zero Cover¶

Definition¶

A minimum zero cover is a smallest set of matrix rows and columns (lines) that together cover all zero entries.

Zeros are independent if no two share a row or a column; a maximum independent zero assignment is a largest set of independent zeros. From such an assignment, a minimum zero cover is found by marking:

Mark every row without an assigned zero.
Mark every column that has a zero in a marked row.
Mark every row whose assigned zero lies in a marked column.
Repeat steps 2 and 3 until nothing new is marked; then cover all marked columns and all unmarked rows.

Interpretation¶

A minimum zero cover counts how many zeros of the reduced table can be used at the same time. By the matching duality quoted in the Examples, the smallest number of lines covering all zeros equals the largest number of zeros with no two in the same row or column. Fewer than $n$ lines therefore prove that no complete zero assignment exists yet.

A 3 by 3 reduced cost matrix with its zeros highlighted and covered by two lines, one row and one column, fewer than three, so the matrix must be adjusted.

The blue zeros sit in row $2$ and column $2$ , so these two red lines cover them all. Every zero lies in row $2$ or column $2$ , and independent zeros can take at most one from each, so at most two exist, for example $(1,2)$ and $(2,1)$ . Since $2<3$ $3$ , the Hungarian algorithm must adjust the table before it can stop.

The marking procedure must start from a maximum assignment of zeros; one to which no zero can be added is not enough. In the figure, $(2,2)$ alone cannot be extended, since the other zeros all lie in row $2$ or column $2$ . Starting the marking from it marks rows $1$ and $3$ , then column $2$ , then row $2$ , and finally all three columns, giving three lines and the false conclusion that a complete zero assignment exists.

A largest set of independent zeros is a largest bipartite matching between rows and columns that uses only zero entries, and the maximum flow construction finds one.

Key Results¶

For an $n\times n$ matrix, $n$ required covering lines indicate that a complete zero-cost assignment exists.
The cover size equals the size of the maximum independent zero assignment.
Rows and columns marked during the search are not the same as the final lines: the final rows are the unmarked ones.
If fewer than $n$ lines are needed, subtract the smallest uncovered entry from all uncovered entries and add it to entries at intersections of covering lines. Repeat the assignment and covering steps until $n$ lines are needed.

Examples¶

In the illustrated matrix, the independent zeros at $(1,2)$ and $(2,1)$ form a maximum assignment of size $2$ . Row 2 and column 2 cover every zero with two lines. Their equal sizes illustrate Kőnig's theorem: the largest number of independent zeros always equals the smallest number of lines covering all zeros (the matrix form of the bipartite matching duality). Since $2<3$ $3$ , the matrix still needs adjustment before a complete zero assignment is possible.
The marking finds this cover. Row 3 has no assigned zero, so it is marked; its zero in column 2 marks column 2; the zero assigned in column 2 is in row 1, so row 1 is marked; row 1 adds no new column. The cover is the marked column 2 and the unmarked row 2.
Course examples (matrices in the course materials, not reproduced here): Week 5 practice 5(b) covers columns 1 and 2 and rows 2 and 3; the ten-job example covers columns 1, 3, 4, 5, 8, 9 and rows 2, 10, eight lines in all.

Prerequisites¶

Bipartite Matching

Sources¶

OR Modelling · Week 5

Aliases: minimum line cover

Last updated: 20 October 2026 03:02