Hungarian Algorithm

Graph Theory · Axiom Academy

Solving the weighted bipartite matching problem optimally in polynomial time using augmenting paths and potential functions. 1. The Weighted Bipartite Matching Problem A bipartite graph has vertices divided into two disjoint sets, with edges only between sets (never within a set). In the weighted version, each edge has a cost or weight. 2. The Assignment Problem Formulation The classic assignment problem assumes we have n workers and n jobs, with a cost matrix C where c ij is the cost of assigning worker i to job j . 3. Key Concept: Feasible Potentials The algorithm uses feasible potentials (also called vertex labels or dual variables) to transform the problem. We assign values u i to workers and v j to jobs such that: The algorithm maintains feasible potentials and gradually builds a perfect matching using only tight edges (edges in the equality subgraph). Initialize potentials: Set u i = min j c ij for each worker i , and v j = 0 for each job j Build initial matching: Find a maximal matching M in the equality subgraph While M is not perfect: a. Select an unmatched worker, start augmenting path search b. Grow an alternating tree from this worker using tight edges c. If augmenting path found: augment the matching (increase |M| by 1) d. If stuck: update potentials to add new tight edges, then retry Return: The perfect matching M with minimum cost 5. Augmenting Paths and Potential Updates

This is the written version of the interactive lesson above. See the full Graph Theory course.