We extend the example of matching students to appropriate jobs by introducing preferences. Now, we aim to find a matching that will fulfill each students preference (to the maximum degree possible).
Finding matchings between elements of two distinct classes is a common problem in mathematics. In this case, we consider weighted matching problems, i.e. we look for matchings with optimal edge weights.
The Hungarian Method, which we present here, will find optimal matchings in bipartite graphs.
Which graph do you want to execute the algorithm on?
Start with an example graph:
Modify it to your desire:
Double click in the area of one of the partitions, in order to add a vertex to that partition. You can create up to 8 nodes in each partition.
In order to create an edge, first click on the origin node, then on the destination node.
You can only create edges between separate partitions. You can change the weight of an edge by double clicking the middle of the edge and entering the new weight.
Daily life contains many problems that can be modeled using matchings in bipartite graphs. Here, we consider weighed proglems in particular
Let's look at the following problem as an example: An CEO is faced with a multitude of tasks that have to be dealt with in his company. However, his employees have diverse qualifications and certain tasks suit some employees more than others. This means that a certain level of efficiency will be assigned for each employee performing a certain task. The CEO obviously wants his company to run as efficiently as possible, thus he has to assign tasks to employees in such a way that the level of efficiency is maximized (to the extend possible) for each task.
We can model this problem as a bipartite graph with vertex sets \(X\) (orange) representing the employees and \(Y\) (red) representing the tasks (see Figure 1). All the following illustrations will use these labelings. The weighed edges between these sets then define the total number of hours that employee \(x\) will need to complete task \(y\). The goal is to find a perfect matching that minimizes the sum of edge weights.
The Hungarian Method
The problem can be solved using the Hungarian Method that was developed in 1955 by Harold W. Kuhn based on the ideas of two hungarian mathematicians (Dénes Kőnig and Jenő Egerváry). Later, the algorithm was improved by James Munkres. It's based on a central theorem. In order to understand this, we will have to introduce some concepts:
Labels
We introduce a simple helper function or label \(l\), that assigns a real number to each vertex in the graph, such that the sum of the labels of two edges is at least as great thatn the weight of the edge \(w\) that connect these vertices (see Figure 2).
\(l(x) + l(y) \ge w(x, y)\)
Equality Graph
Using these labels, we can construct an equality graph \(G_l = (V, E_l)\) that contains all nodes from the original Graph. However, the edge set will only contain those edges that have exactly the weight of the sum of the labels of their corresponding vertices (Figure 3).
Now back to the theorem mentioned above: The Kuhn-Munkres theorem states that any perfect matching in the equality graph is maximal in the original graph. Thus, the problem of finding an optimal matching can be reduced to finding a perfect matching in the equality graph.
Some more information before we look at the algorithm itself:
The Hungarian Method as described here will find maximal matchings, meaning matchings with their total edge weights as great as possible. This implies that we will have to remodel the problem described in the beginning: To do so, we "mirror" the edge weights by changing the sign, i.e. turning \(w(x,y)\) into \(-w(x,y)\).
Furthermore, the bipartite graph that we run the algorithm on must be complete, thus the number of nodes in \(X\) and \(Y\) must be the same and there must be an edge between any two vertices that lie in different partitions. In our example, this would not be the case, if some employee is not qualified to work on some specific job. In this case, we will introduce neutral vertices and edges with weight \(0\), such that the graph becomes complete. If any of the neutral elements are contained in the matching that the algorithm ultimately finds, we can simply remove them again.
The Execution of the Algorithm
The algorithm uses an iterative approach for finding a perfect matching in the equality graph. It starts with an empty matching and tries to improve the current matching in every step, until perfection is reached.
In the beginning, the algorithm specifies a label for each node. Every node in \(X\) is assigned the weight of its heaviest edge, each vertex in \(Y\) begins with the label \(0\). Using these labels, the algorithm then constructs the equality graph. For the next steps, we must first introduce some more concepts:
Alternating and Augmenting Paths
We call a vertex matched, iff it has an edge that is contained in the current matching; otherwise we call it free (compare Figure 4).
An alternating path is a sequence of edges where the edges alternate between being contained and not contained in the matching \(M\). An alternating path is called augmenting, if both its origin and destination nodes are free (see Figure 6).
In order to improve on the existing (still empty) matching, the algorithm selects a node in \(X\) that does not yet have a matching partner. Starting in this node, we then look for an augmenting path: In order to do this, the algorithm builds up an alternating path step by step, until the path either becomes augmenting or no further qualified edges exist. We partition the nodes that have been visited by this procedure into the sets \(S\) for visited nodes in \(X\) and \(T\) for nodes in \(Y\), respectively.
However, it is not always possible to find an augmenting path. If this is the case, the algorithm must improve the labels assigned to the vertices. The improvement must be performed in a way such that the current matching is preserved in the equality graph. Furthermore, the equality graph must be extended with additional edges in such a way that a new alternating path can be constructed. This can be insured by first specifying a value \(\Delta\) by considering all pairs of visited nodes \(s \in S\) and unvisited nodes \(y \in Y \setminus T\) and calculating the minimum of the sum of their respective labels minus the weight of the edge between them.
\(\Delta = \min\limits_{s \in S\ \wedge\ y \in Y \setminus T}\{l(s) + l(y) - w(s,y)\}\)
The labels of all nodes can now be adjusted using \(\Delta\) before defining the new equality graph and in turn surching for augmenting paths.
\(\begin{equation}
l^\prime(v) =
\begin{cases}
l(v) - \Delta & v \in S\\
l(v) + \Delta & v \in T \\
l(v) & otherwise
\end{cases}
\end{equation}\)
If the path does find an augmenting path, it improves on the current matching by adding the edges of the path which are not currently contained in the matching and removing those from the path that currently are. This step is being repeated until each node has a matching partner and the matching is thus perfect. Using the theorem given above, the matching found in this way must then be maximal in terms of edge weights.
What does the (Pseudo-)Code of the algorithm look like?
Input: Complete, bipartite, weighed graph \(G=(V,E)\) Output: Optimal Matching \(M \subseteq E\) in terms of edge weights, represented as a list of edges
BEGIN
Initialize Labels
Construct Equality Graph
WHILE Matching not Optimal DO
Find Free Node as Root of an Alternating Path
WHILE Path not augmenting DO
Construct Alternating Path in Equality Graph
IF No Alternating Path found
THEN Improve Labels and Construct New Equality Graph
END
Improve Matching
END
END
How fast is the algorithm?
Speed of algorithms
The speed of an algorithm is the total number of individual steps which are performed during the execution.
These steps are for example:
Assignments – Set distance of a node to 20.
Comparisons – Is 20 greater than 23?
Comparison and assignment – If 20 is greater than 15, set variable
n
to 20
Simple Arithmetic Operations – What is 5 + 5?
Since it can be very difficult to count all individual steps, it is desirable to only count the approximate magnitude of the number of steps. This is also called the running time of an algorithm. Particularly, it is interesting to know the running time of an algorithm based on the size of the input (in this case the number of the vertices and the edges of the graph).
Running Time of the Hungarian Method
There are several ways to implement the Hungarian Method that differ in their respective running times. Here we consider the fasted method.
We assume that we are given a complete bipartite graph \(G = (V, E)\) with \(V = X \cup Y \land X \cap Y = \emptyset\) and an empty initial matching \(M\). For ease of notation we further define \(|V| = n, |X| = n_1, |Y| = n_2\).
At initialization, the graph is extended using neutral edges and an initial matching is found. In order to do so, all edges must be considered. In a complete bipartite graph there are \(O(n_1 * n_2)\) of them.
The algorithm will then try to add one additional node to the matching in each iteration. Thus there can be at most \(n\) repititions. In each iteration the following calculations are performed:
Constructing the equality graph: This also makes it necessary to consider all edges: \(O(n_1 * n_2)\).
Finding a new root will in the worst case require \(O(n)\) operations.
In order to construct an augmenting path, all edges of the equality graph are considered, starting at the root node. In the worst case, it can contain all edges. Thus we have an additional complexity of \(O(n_1 * n_2)\).
The augmenting path will have a maximum length of \(n\). Thus the subsequent adding and removing of edges to/from the matching will need \(O(n)\) steps.
Checking, whether the found matching is perfect can be achieved by simply comparing the number of edges: \(O(1)\).
The most significant calculations must be performed whenever no augmenting path can be found. In this case, a new equality graph must be constructed after altering the labels and calculating a new Delta \(\Delta\). However, specifying a new equality graph does not guarantee that an augmenting path can be constructed. In total, however, only \(O(n)\) edges can be added to the equality graph by improving the labels. Using trivial implementation, this process has a complexity of \(O(n^4)\), using intelligent caching of specific values, however, the time complexity of calculating the Delta can be reduced to \(O(n^2)\).
In total, the algorithm then has a cubic running time of \(O(n^3)\).
How can we prove that the algorithm will always give a correct result?
The correctness of the algorithm is based in the Kuhn-Munkres-Theorem. It states that perfect matchings in equality graphs are optimal in the original graph, i.e. have maximal total edge weight.
Formal Proof
Let the labels \(l: V \to \mathbb{R}\) be feasible, \(M' \subseteq E\) be an arbitrary perfect matching and \(M \subseteq E\) an optimal matching with associated maximal weight \(w(M)\).
\(
\begin{align}
w(M')
&= \sum\limits_{(x,y) \in M'} w(x,y) &&\text{(Total weight equals sum of edge weights)}
\\ &\le \sum\limits_{(x,y) \in M'} (l(x) + l(y)) &&\text{(By the label formula)}
\\ &= \sum\limits_{v \in V} l(v) &&\text{(Since M' is perfect, each label is contained in the sum exactly once)}
\\ &= \sum\limits_{(x,y) \in M} (l(x) + l(y)) &&\text{(analogously, since M is also perfect)}
\\ &= \sum\limits_{(x,y) \in M} w(x,y) &&\text{(All edges from M are contained in the equality graph)}
\\ &= w(M) && \square
\end{align}
\)
Where can I find more information on graph algorithms??
Other graph algorithms are explained on the Website of Chair M9 of the TU München.
A last remark about this page's content, goal and citations
Chair M9 of Technische Universität München does research in the fields of discrete mathematics, applied geometry and the mathematical optimization of applied problems. The algorithms presented on the pages at hand are very basic examples for methods of discrete mathematics (the daily research conducted at the chair reaches far beyond that point). These pages shall provide pupils and students with the possibility to (better) understand and fully comprehend the algorithms, which are often of importance in daily life. Therefore, the presentation concentrates on the algorithms' ideas, and often explains them with just minimal or no mathematical notation at all.
Please be advised that the pages presented here have been created within the scope of student theses, supervised by Chair M9. The code and corresponding presentation could only be tested selectively, which is why we cannot guarantee the complete correctness of the pages and the implemented algorithms.
Naturally, we are looking forward to your feedback concerning the page as well as possible inaccuracies or errors. Please use the suggestions link also found in the footer.
To cite this page, please use the following information:
Title: The Hungarian Method
Authors: Mark J. Becker, Wolfgang F. Riedl, Aleksejs Voroncovs; Technische Universität München
