Hungarian Algorithm

Hungarian algorithm (also known as the Kuhn–Munkres algorithm or Munkres assignment algorithm) is a primal–dual combinatorial optimization procedure in computation and algorithms that solves the linear assignment problem—finding a minimum-cost (or maximum-weight) perfect matching in an edge-weighted bipartite graph—in O(V³) strongly polynomial time. Developed and published by Harold W. Kuhn in 1955 and refined by James Munkres in 1957, the algorithm was named by Kuhn in honor of the Hungarian mathematicians Dénes Kőnig and Jenő Egerváry, whose 1931 theorems on bipartite vertex covers and weighted matrix reductions provided its mathematical foundation; posthumous archival discoveries in 2006 revealed that Carl Gustav Jacob Jacobi had formulated an equivalent method in Latin manuscripts published in 1890.

As the historical prototype of the primal–dual method in linear programming and computational complexity theory, the Hungarian algorithm maintains a feasible dual solution consisting of vertex potentials u_i and v_j alongside a partial primal matching M restricted to zero-reduced-cost tight edges satisfying u_i + v_j = c_i,j. In each phase, it either augments the matching M inside the tight equality subgraph or adjusts the vertex potentials along an alternating tree to bring new tight edges into the equality subgraph until a perfect matching of size n is achieved.

The Linear Assignment Problem and Birkhoff Polytope

Given an n × n real cost matrix C = (c_i,j) representing the cost of assigning worker (left vertex) i ∈ {1, …, n} to task (right vertex) j ∈ {1, …, n}, the minimum-cost assignment problem seeks a bijection (permutation) π : {1, …, n} → {1, …, n} minimizing total cost ∑_i=1ⁿ c_i,π(i). Formulated as a linear program over binary decision variables x_i,j ∈ {0, 1}, the primal linear program is:

subject to:

1. ∑_j=1ⁿ x_i,j = 1 for all i ∈ {1, …, n} (each row assigned once),
2. ∑_i=1ⁿ x_i,j = 1 for all j ∈ {1, …, n} (each column assigned once),
3. x_i,j ≥ 0 for all i, j ∈ {1, …, n}.

Because the constraint matrix of a bipartite graph is totally unimodular, the Birkhoff–von Neumann Theorem guarantees that the feasible polytope of doubly stochastic matrices has integral extreme points (permutation matrices).

Dual Vertex Potentials and Complementary Slackness

Introducing unconstrained real dual variables (called vertex potentials or labels) u₁, …, u_n ∈ ℝ for the rows and v₁, …, v_n ∈ ℝ for the columns yields the dual linear program:

subject to the dual feasibility constraints:

Define the non-negative reduced cost (or slack) of edge (i, j) as c̄_i,j = c_i,j − u_i − v_j ≥ 0. An edge (i, j) is called tight (or admissible) if c̄_i,j = 0, meaning u_i + v_j = c_i,j. The equality subgraph G_u,v = (U ∪ W, E_u,v) consists of all tight edges:

By linear programming complementary slackness, if (u, v) is a feasible dual potential and M is a perfect matching (n edges) contained inside the equality subgraph E_u,v, then M is a minimum-cost assignment:

Because weak duality states that every assignment has cost at least ∑ u_i + ∑ v_j, equality proves optimality of both M and (u, v).

Matrix vs. Graph-Theoretic Primal–Dual Formulation

While early textbook presentations described row and column zero-covering steps on the matrix C (O(n⁴) naive time), Jack Edmonds and Richard Karp (1972) and independently Dinic and Kronrod (1969) formulated the modern O(n³) graph-theoretic algorithm by maintaining minimum column slacks:

1. Dual Initialization: Set u_i ← min_j c_i,j for each row i and v_j ← min_i (c_i,j − u_i) for each column j. Start with an empty matching M = ∅ inside G_u,v.
2. Phase Loop (n Phases): While |M| < n, select an unmatched left vertex r ∈ U and grow a Hungarian alternating tree T rooted at r inside G_u,v. Let S ⊆ U be the set of left vertices currently in T (initially S = {r}) and T_W ⊆ W be the set of right vertices currently in T (initially T_W = ∅).
3. Slack Array Maintenance: For every column j ∈ W \ T_W, maintain its minimum slack to the current tree S:

together with the minimizing parent vertex argmin_{i ∈ S}.

1. Dual Potential Update and Tree Growth: Compute the step size Δ = min_{j ∈ W \ TW} slack[j] > 0 (or Δ = 0 if a tight edge to W \ T_W already exists). Update potentials and slacks in O(n) time:
   • For all i ∈ S: u_i ← u_i + Δ
   • For all j ∈ T_W: v_j ← v_j − Δ
   • For all j ∈ W \ T_W: slack[j] ← slack[j] − Δ

Note that edges inside S × T_W remain tight ((u_i + Δ) + (v_j − Δ) = u_i + v_j), while at least one column j* ∈ W \ T_W reaches slack[j*] = 0 and becomes connected to S by a new tight edge.

1. Tree Extension or Augmentation:
   • If j* is unmatched, an augmenting path from r to j* in G_u,v has been found! Flip the matching along this path (M ← M ⊕ P), increasing |M| by 1, and end the phase.
   • If j* is already matched to some row i* ∈ U \ S, add j* to T_W and i* to S, and update slack[j] ← min(slack[j], c_i*,j − u_i* − v_j) for all j ∈ W \ T_W in O(n) time.

Because each of the n phases adds at most n vertices to S and T_W, and each vertex addition updates the slack array in O(n) time, each phase takes O(n²) time. Across all n phases, the total runtime is strongly polynomial O(n³) (or O(V E + V² log V) on sparse bipartite graphs when implemented as successive shortest augmenting paths via potential-reweighted Dijkstra's algorithm with Fibonacci heaps, Fredman and Tarjan 1987).

Comparative Complexity of Assignment and Weighted Matching Solvers

1. Multi-Object Visual Tracking (Simple Online and Realtime Tracking / DeepSORT): Autonomous vehicle perception and cellular microscopy tracking pipelines use the Hungarian algorithm at every video frame to match Kalman-predicted bounding boxes against newly detected objects using Intersection-over-Union (IoU) and Mahalanobis appearance distances.
2. Single-Cell Transcriptomics and Spatial Alignment: Computational biology tools align cell clusters across multi-omic batches and map single-cell RNA-seq profiles to spatial transcriptomic landmarks via optimal transport and minimum-cost bipartite matching.
3. Quantum Chemistry and Orbit Localization: Molecular orbital correspondence across geometry optimization steps and atom-to-atom reaction mapping in chemoinformatics rely on the Hungarian algorithm to minimize root-mean-square coordinate displacement.

How is the Hungarian algorithm adapted for maximum-weight bipartite matching?

To maximize ∑ w_i,j x_i,j, either negate all weights (c_i,j = W_max − w_i,j where W_max = max_i,j w_i,j) and solve for minimum cost, or reverse the dual inequality to u_i + v_j ≥ w_i,j and minimize ∑ u_i + ∑ v_j.

Why are vertex potentials used instead of running the Bellman–Ford algorithm at every step?

After the initial potentials satisfy c_i,j − u_i − v_j ≥ 0, all reduced edge weights in the residual network are non-negative. This allows shortest augmenting paths to be found in O(V²) (or O(E + V log V)) time via Dijkstra's algorithm rather than O(V E) time via the Bellman–Ford algorithm.

1. Kuhn, H. W. (1955). "The Hungarian method for the assignment problem." Naval Research Logistics Quarterly, 2(1–2), 83–97. https://doi.org/10.1002/nav.3800020109
2. Munkres, J. (1957). "Algorithms for the assignment and transportation problems." Journal of the Society for Industrial and Applied Mathematics, 5(1), 32–38. https://doi.org/10.1137/0105003
3. Edmonds, J., & Karp, R. M. (1972). "Theoretical improvements in algorithmic efficiency for network flow problems." Journal of the ACM, 19(2), 248–264. https://doi.org/10.1145/321694.321699
4. Jonker, R., & Volgenant, A. (1987). "A shortest augmenting path algorithm for dense and sparse linear assignment problems." Computing, 38(4), 325–340. https://doi.org/10.1007/BF02278710