7.6.1.3. Implementing Each Iteration

Each iteration in a phase now needs to pick the vertex \(w \in \bar Y\) with minimum slack and move it to \(Y\).

By Invariant 7.23, the vertex with minimum slack also has minimum priority in \(Q\). Thus, we can identify \(w\) in constant time using a FindMin operation.

Also by Invariant 7.23, we have \(\delta_w = q_w - \delta_0\), so we can compute \(\delta_w\) in constant time. Note that since \(w\) is the vertex with minimum slack, we have \(\delta_w = \delta\). Next we need to either update \(\pi\) if \(\delta > 0\) or grow \(F^\pi\) if \(\delta = 0\). We will assume for now that \(\delta = \delta_w < \infty\). As we prove in Section 7.6.1.4, if \(\delta_w = \infty\), then there does not exist a perfect matching in \(G\), so this is how we detect that there exists no perfect matching and abort the algorithm in this case.

Updating \(\boldsymbol{\pi}\)

If \(\delta > 0\), then we need to

• Increase \(\pi_u\) by \(\delta\) for every vertex \(u \in X\),
• Decrease \(\pi_w\) by \(\delta\) for every vertex \(w \in Y\), and
• Decrease \(\delta_{w'}\) by \(\delta\) for every vertex \(w' \in \bar Y\).

We can do this in constant time by adding \(\delta\) to \(\delta_0\). Indeed, by Invariant 7.23, we have

• \(\pi_u = \pi'_u + \delta_0\) for every vertex \(u \in X\). Increasing \(\delta_0\) by \(\delta\) without changing \(\pi'_u\) thus increases \(\pi_u\) by \(\delta\).

• \(\pi_{w'} = \pi'_{w'} - \delta_0\) for every vertex \(w' \in Y\). Increasing \(\delta_0\) by \(\delta\) without changing \(\pi'_{w'}\) thus decreases \(\pi_{w'}\) by \(\delta\).

• \(\delta_{w'} = q_{w'} - \delta_0\) for every vertex \(w' \in \bar Y\). Increasing \(\delta_0\) by \(\delta\) without changing \(q_{w'}\) thus decreases \(\delta_{w'}\) by \(\delta\).

Growing \(\boldsymbol{F^{\pi}}\)

As in the \(O\bigl(n^3\bigr)\)-time implementation of the Hungarian algorithm, we start by moving \(w\) from \(\bar Y\) to \(Y\). This no longer takes constant time, because we need to maintain our data structures and Invariant 7.23, but we can implement this step in \(O(\lg n)\) time:

• First we remove \(w\) from \(Q\) using a DeleteMin operation. This is what takes \(O(\lg n)\) time. Since \(Q\) is our representation of \(\bar Y\), this removes \(w\) from \(\bar Y\) and, thus, adds it to \(Y\).

• To restore Invariant 7.23, we need to update \(\pi'_w\) so that \(\pi_w = \pi'_w - \delta_0\). Since we just removed \(w\) from \(\bar Y\), we currently have \(\pi_w' = \pi_w\). Thus, we ensure that \(\pi_w = \pi'_w - \delta_0\) by increasing \(\pi'_w\) by \(\delta_0\). This clearly takes constant time.

The next steps depend on whether \(w\) is matched.

If \(w\) is unmatched, we have created a tight augmenting path \(P_w\) in \(F^\pi\), and this is the last iteration of the current phase. Note that our data structures do not help us to reduce the cost of reporting \(P_w\) to less than \(O(n)\). However, since this is the last iteration of the phase, we incur this \(O(n)\) cost only once per phase. Since the initialization of the phase already takes \(O(n + m)\) time, adding an \(O(n)\) cost to report the path \(P_w\) to the overall cost of the phase increases the cost of the phase by at most a constant factor.

If \(w\) is matched, then we need to move \(w\)'s mate \(u\) from \(\bar X\) to \(X\) and update the priorities of its neighbours in \(\bar Y\) accordingly:

• First we set \(p_u = w\), thereby making \(u\) the child of \(w\) in \(F^\pi\). This clearly takes constant time.

• Next we restore the part of Invariant 7.23 that states that every vertex \(u' \in X\) has potential \(\pi_{u'} = \pi'_{u'} + \delta_0\). All vertices in \(X \setminus \{u\}\) already satisfy this invariant. To ensure that \(u\) satisfies the invariant, observe that we just removed \(u\) from \(\bar X\). Thus, by Invariant 7.23, we have \(\pi'_u = \pi_u\). By decreasing \(\pi'_u\) by \(\delta_0\), we establish the condition that \(\pi_u = \pi'_u + \delta_0\). This clearly takes constant time.

• Finally, we restore the invariant that the slack of every vertex \(w' \in \bar Y\) is \(\delta_{w'} = q_{w'} - \delta_0\). Note that moving \(u\) from \(\bar X\) to \(X\) leaves the slack of \(w'\) unchanged if \((u, w') \notin E\). If \((u, w') \in E\), then the new slack of \(w'\) is \(\delta_{w'} = \min(\delta_{w'}, c_{u,w'} - \pi_u - \pi_{w'})\).

  By Invariant 7.23, we can compute the current slack \(\delta_{w'}\) of \(w'\) by subtracting \(\delta_0\) from the current priority \(q_{w'}\) of \(w'\). We can also compute \(\pi_u\) as \(\pi'_u + \delta_0\) and \(\pi_{w'}\) as \(\pi'_{w'}\) because \(u \in X\) and \(w' \in \bar Y\). Next we compare \(\delta_{w'}\) with \(c_{u,w'} - \pi_u - \pi_w\).

  If \(\delta_{w'} \le c_{u,w'} - \pi_u - \pi_{w'}\), then the slack of \(w'\) does not change as the result of moving \(u\) from \(\bar X\) to \(X\): the edge \((u, w')\) is not the minimum-slack edge connecting \(w'\) to \(X\). Thus, no further updates of \(w'\) are required.

  If \(\delta_{w'} > c_{u,w'} - \pi_u - \pi_{w'}\), then \((u,w')\) is the new minimum-slack edge connecting \(w'\) to \(X\). We start by setting \(p_{w'} = u\). This takes constant time. Then we need to update \(q_{w'}\) to reflect the decrease of \(\delta_{w'}\). Since Invariant 7.23 requires that \(\delta_{w'} = q_{w'} - \delta_0\) and we now have \(\delta_{w'} = c_{u,w'} - \pi_u - \pi_{w'}\), we need to decrease \(q_{w'}\) to \(c_{u,w'} - \pi_u - \pi_{w'} + \delta_0\), which we do using a DecreaseKey operation. On a Fibonacci Heap or Thin Heap, this operation takes amortized constant time.

We have shown the following lemma:

Lemma 7.25: Each iteration of the Hungarian algorithm updates the potential function \(\pi\), moves a matched vertex \(w\) from \(\bar Y\) to \(Y\) and its mate \(u\) from \(\bar X\) to \(X\), or moves an unmatched vertex \(w\) from \(\bar Y\) to \(Y\) and reports the resulting augmenting path \(P_w\) in \(F^\pi\). In the first case, the iteration takes constant time. In the second case, it takes amortized \(O(\lg n + \deg(u))\) time. In the last case, the iteration takes \(O(n)\) time and is the last iteration of the current phase.