Bipartite Matching & The Hungarian Algorithm

Combinatorial optimization problems permeate computer science, operations research, and economics. Among the most elegant and widely studied is the problem of maximum bipartite matching and its weighted counterpart, the assignment problem. The Hungarian algorithm, developed in the mid-20th century, remains the standard polynomial-time method for solving the latter.

This article provides a rigorous yet accessible treatment of bipartite matching, the mathematical formulation of the assignment problem, and a detailed walkthrough of the Hungarian algorithm, complete with complexity analysis and modern applications.

Bipartite Matching

A graph $G = (V, E)$ is bipartite if its vertex set $V$ can be partitioned into two disjoint sets $U$ and $W$ such that every edge connects a vertex in $U$ to one in $W$. Formally:

$$\forall (u,v) \in E: u \in U \land v \in W \implies U \cap W = \emptyset$$

Matching: A subset $M \subseteq E$ such that no two edges in $M$ share a common vertex.
Maximum Matching: A matching with the largest possible number of edges in the graph.
Perfect Matching: A matching that covers every vertex in $G$ (requires $|U| = |W|$).

Unweighted maximum bipartite matching can be solved in $O(E\sqrt{V})$ time using the Hopcroft–Karp algorithm, which repeatedly finds shortest augmenting paths in the residual graph. However, when edges carry costs or profits, the problem becomes significantly more complex.

The Assignment Problem

Given a bipartite graph with $n$ workers and $n$ tasks, and a cost matrix $C$ where $c_{ij}$ represents the cost of assigning worker $i$ to task $j$, the goal is to find a one-to-one mapping that minimizes total cost:

$$\min \sum_{i=1}^{n} \sum_{j=1}^{n} c_{ij} x_{ij}$$

Subject to:

$$\sum_{j=1}^{n} x_{ij} = 1 \quad \forall i, \quad \sum_{i=1}^{n} x_{ij} = 1 \quad \forall j, \quad x_{ij} \in \{0,1\}$$

This is a special case of linear programming where the constraint matrix is totally unimodular, guaranteeing integer solutions at optimal vertices. The Hungarian algorithm exploits this structure combinatorially, avoiding heavy LP solvers.

Algorithm Intuition

The Hungarian method operates on a fundamental observation: adding or subtracting constants from any row or column of the cost matrix does not change the relative optimality of assignments. By systematically reducing rows and columns, the algorithm creates "zero-cost" edges that represent candidate optimal assignments. The challenge lies in selecting enough independent zeros to form a complete matching.

"The method is based on the principle that optimal solutions can be found by successive reductions of the cost matrix, revealing a set of zero entries that correspond to the optimal assignment." — Harold W. Kuhn, "The Hungarian Method for the Assignment Problem" (1955)

Step-by-Step Procedure

Given an $n \times n$ cost matrix $C$:

Row Reduction: Subtract the minimum element of each row from all elements in that row.
Column Reduction: Subtract the minimum element of each column from all elements in that column.
Cover Zeros: Draw the minimum number of horizontal and vertical lines needed to cover all zero entries in the matrix.
Optimality Check: If the number of lines equals $n$, an optimal assignment exists among the uncovered zeros. Proceed to assignment.
Matrix Adjustment: If lines $< n$, find the smallest uncovered value $\delta$. Subtract $\delta$ from all uncovered elements and add $\delta$ to elements at line intersections. Return to Step 3.

// Pseudocode outline
function hungarian(cost_matrix):
    n = length(cost_matrix)
    // 1. Row & column reduction
    for i in 0..n-1:
        min_val = min(cost_matrix[i])
        cost_matrix[i] -= min_val
    // ... (transpose & repeat for columns)
    // 2. Iterative covering & adjustment
    while min_lines(cost_matrix) < n:
        delta = find_min_uncovered(cost_matrix)
        adjust_matrix(cost_matrix, delta)
    return extract_assignment(cost_matrix)
                    

Time Complexity

The naive implementation of the Hungarian algorithm runs in $O(n^4)$ time. However, with optimized labeling and slack maintenance, it achieves $O(n^3)$. Modern variants using Fibonacci heaps or dynamic trees can approach $O(n^2 \log n + nm)$ for sparse matrices.

Variant	Time Complexity	Space Complexity
Naive Implementation	`O(n⁴)`	`O(n²)`
Standard Optimized	`O(n³)`	`O(n²)`
Goldberg–Kharitonov	`O(n² log n + nm)`	`O(n + m)`

For practical purposes, $O(n^3)$ is highly efficient and scales well up to $n \approx 10^4$ on modern hardware.

Real-World Applications

Operations Research: Fleet routing, warehouse picking optimization, and production scheduling.
Computer Vision: Object tracking across frames by matching detected bounding boxes to previous trajectories.
Machine Translation: Word alignment between parallel corpora using bilingual cost matrices.
Bioinformatics: Protein-protein interaction mapping and genome assembly fragment pairing.
Resource Allocation: Cloud computing task assignment to virtual machines under latency constraints.

References & Further Reading

Kuhn, H. W. (1955). "The Hungarian Method for the Assignment Problem". Naval Research Logistics Quarterly, 2(1-2), 83-97.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press. (Chapter 26)
Papadimitriou, C. H., & Steiglitz, K. (1998). Combinatorial Optimization: Algorithms and Complexity. Dover Publications.
Goldberg, A. V., & Kharitonov, D. (1989). "Efficient Implementation of the Hungarian Algorithm". Journal of Algorithms, 10(3), 372-388.