Zero-Cost Matching via Maximum Flow¶

Definition¶

To obtain a maximum zero-cost matching, create a source $S$, one vertex for each matrix row, one for each column, and a sink $T$. Add source-to-row edges, row-to-column edges exactly where the matrix entry is zero, and column-to-sink edges. Give every edge capacity 1 and compute an integral maximum flow.

Interpretation¶

After the reductions of the Hungarian algorithm, the question is how many zeros can be chosen with no two in the same row or column. This construction answers it with a maximum flow: each unit of flow from $S$ to $T$ passes through one row and one column joined by a zero, so it selects one zero-cost pair.

Rows $r_1$ and $r_3$ have a zero only in column 2, so both need $c_2$, which can pass on at most one unit to $T$. The green flow uses $r_1\to c_2$ and $r_2\to c_1$ and has value $2$. A flow of value $3$ would need all three rows, so it does not exist. Only two independent zeros can be selected, fewer than the three needed for a complete assignment.

Capacity $1$ on each edge $S\to r_i$ lets every row send at most one unit, so no row is used twice; capacity $1$ on each edge $c_j\to T$ does the same for the columns. These are exactly the conditions of a bipartite matching. To read the flow as a set of pairs, every edge must carry $0$ or $1$; the augmenting path algorithm started from zero flow guarantees this for integer capacities.

When the flow value is smaller than the number of rows, the Hungarian algorithm needs a minimum zero cover. It uses as many lines as there are independent zeros, here $2$, and tells which entries to adjust next.

Key Results¶

• The maximum flow value is the maximum number of simultaneous zero-cost assignments.
• Read selected pairs from row-to-column edges carrying flow 1.
• The augmenting path algorithm starting at zero preserves integrality for these integer capacities.

Examples¶

The figure’s zero pairs are $(1,2),(2,1),(2,2),(2,3),(3,2)$. Its integral maximum flow is 2, so only two independent zeros can be assigned, fewer than the three required for a complete assignment. The minimum cut also determines a minimum zero cover; further Hungarian adjustment is needed.

• The five-job practice matrix admits four zero-cost pairs.
• One such matching is jobs 1, 2, 3, 4 to machines 1, 4, 3, 2.

Prerequisites¶

• Bipartite Matching
• Augmenting Path Algorithm

Related Concepts¶

• Minimum Zero Cover
• Hungarian Algorithm

Sources¶

• OR Modelling · Week 5

Last updated: 20 October 2026 03:02