7.6.1.1. The Necessary Data Structures

Recall that each iteration of the Hungarian algorithm finds the vertex \(w \in \bar Y\) with minimum slack \(\delta_w\), moves it to \(Y\) and moves its mate from \(\bar X\) to \(X\) if \(w\) has a mate (is matched). The first thing we need to do to achieve a sublinear cost per iteration is to avoid inspecting all vertices in \(\bar Y\) to find the one with minimum slack. We do this by maintaining a priority queue \(Q\) storing the vertices in \(\bar Y\), ordered by their current slack values \(\delta_w\). This allows us to find the vertex with minimum slack \(\delta_w\) in constant time using a FindMin operation.

When moving a vertex \(u\) from \(\bar X\) to \(X\) and when updating \(\pi\), we also need to update the slack values of the vertices in \(\bar
Y\). Moving a vertex \(u\) from \(\bar X\) to \(X\) does not pose any problems: Given the right priority queue implementation—for example, a Fibonacci Heap or Thin Heap—the DecreaseKey operation necessary to update the priority of every vertex in \(\bar Y\) as a result of having a new neighbour \(u\) in \(X\) takes constant amortized time. Thus, the amortized cost of moving a vertex from \(\bar X\) to \(X\) is \(O(\deg(u))\) (because only the priorities of neighbours of \(u\) need to be updated), which is within the cost per iteration we aim to achieve.

Updating \(\pi\) seems to pose a greater challenge because raising \(\pi_u\) by \(\delta\) for every vertex \(u \in X\) decreases \(\delta_w\) by \(\delta\) for every vertex \(w \in \bar Y\). Thus, if we wanted to maintain the invariant that the priority in \(Q\) of every vertex in \(\bar Y\) is its slack \(\delta_w\), then the cost of updating \(\pi\) would be \(\Omega(|Y|)\), which could be linear in \(n\). To avoid this, observe that I was careful in phrasing what \(Q\) stores above: I said that \(Q\) stores the vertices in \(\bar Y\) ordered by their slack values. I didn't say that their priorities are the slack values. Note that when we increase \(\pi_u\) by \(\delta\) for every vertex \(u \in X\), the slack value \(\delta_w\) changes by the same amount \(\delta\) for every vertex \(w \in \bar Y\). Thus, the relative ordering of the vertices in \(\bar Y\) with respect to their slack values does not change. As a result, we do not need to update any priorities in \(Q\) if all we want to guarantee is that the vertices in \(Q\) are ordered by their slack values. To be able to reconstruct each vertex's slack value from its priority in \(Q\), we maintain a slack adjustment \(\delta_0\), which has the property that the slack of every vertex \(w \in \bar Y\) is its priority in \(Q\) minus this slack adjustment. By adding \(\delta\) to \(\delta_0\), we can (implicitly) decrease the slack values of all vertices \(w \in \bar Y\) by \(\delta\) in constant time.

Let's put the bits and pieces together and give a complete list of the data structures the algorithm maintains:

• For every vertex \(z \in X \cup Y\), we store its parent \(p_z\) in \(F^\pi\), just as in the \(O\bigl(n^3\bigr)\)-time version of the Hungarian algorithm. For every unmatched vertex \(u \in U\), its parent is \(p_u = \textrm{NULL}\).

• For every vertex \(w \in \bar Y\), we store its "parent" \(p_w\), which is the vertex \(p_w \in X\) such that the edge \((p_w, w)\) has minimum slack among all edges connecting \(w\) to a vertex in \(X\). As in the \(O\bigl(n^3\bigr)\)-time version of the Hungarian algorithm, \(p_w\) is the vertex that becomes \(w\)'s parent in \(F^\pi\) once we move \(w\) to \(Y\).

• We store a slack adjustment \(\delta_0\), a single real number.

• We store an adjusted potential \(\pi'_z\) for every vertex \(z \in U \cup W\). Invariant 7.23 below states how the potential \(\pi_z\) of each vertex \(z \in U \cup W\) can be computed in constant time from \(\pi'_z\) and the slack adjustmest \(\delta_0\).

• We maintain a priority queue \(Q\) storing all vertices in \(\bar Y\). Let \(q_w\) be the priority of each vertex \(w \in Q\).

To use these data structures to implement the Hungarian algorithm, we maintain the following invariant:

Invariant 7.23:

• For every vertex \(z \in \bar X \cup \bar Y\), its potential \(\pi_z\) equals \(\pi'_z\).
• For every vertex \(u \in X\), its potential \(\pi_u\) is \(\pi_u' + \delta_0\).
• For every vertex \(w \in Y\), its potential \(\pi_w\) is \(\pi_w' - \delta_0\).
• For every vertex \(w \in \bar Y\), its slack is \(\delta_w = q_w - \delta_0\).