7.6.1.2. Initialization of Each Phase

The initialization of each phase looks very similar to that of the \(O\bigl(n^3\bigr)\)-time implementation of the Hungarian algorithm:

• We start by setting \(\pi'_z = \pi_z\) for every vertex \(z \in U \cup W\) and setting \(\delta_0 = 0\). This establishes the invariants that \(\pi_z = \pi'_z\) for every vertex \(z \in \bar X \cup \bar Y\), \(\pi_u = \pi'_u + \delta_0\) for every vertex \(u \in X\), and \(\pi_w = \pi'_w - \delta_0\) for every vertex \(w \in Y\), no matter how we choose \(X\), \(Y\), \(\bar X\), and \(\bar Y\).

• As in the \(O\bigl(n^3\bigr)\)-time implementation of the Hungarian algorithm, we choose \(X\) to be the set of all unmatched vertices in \(U\), \(\bar X = U \setminus X\), \(Y = \emptyset\), and accordingly, \(\bar Y = W\). For each vertex \(u \in U\), we set \(p_u = \textrm{NULL}\). For each vertex \(w \in \bar Y\), we set \(p_w = \textrm{argmin}_{u \in X}(c_{u,w} - \pi_u - \pi_w)\). This establishes the correct parent pointers for all vertices in \(G\).

• Finally, we calculate \(\delta_w = \min (\{\infty\} \cup \{c_{u,w} - \pi_u - \pi_w \mid (u, w) \in E, u \in X\})\) for every vertex \(w \in \bar Y\) and insert \(w\) into \(Q\) with priority \(q_w = \delta_w\). Since \(\delta_0 = 0\), this establishes the invariant that \(\delta_w = q_w - \delta_0\) for every vertex \(w \in \bar Y\). Note that \(\delta_w = \infty\) if \(w\) has no neighbour in \(X\).

After this initialization, Invariant 7.23 holds.

The cost of the initialization is easily seen to be \(O(n + m)\): Initializing \(\delta_0\) and the adjusted potentials of all vertices in \(G\) takes \(O(n)\) time, as does initializing the parent pointers of all vertices not in \(\bar Y\). Computing \(q_w\) and \(p_w\) for each vertex \(w \in \bar Y\) takes \(O(\deg(w))\) time because it requires inspecting each edge incident to \(w\). Since there are \(m\) edges in \(G\), this takes \(O(m)\) time. If we use a Fibonacci Heap or Thin Heap as the priority queue implementation, then inserting each vertex \(w \in \bar Y\) into \(Q\), with priority \(q_w\), takes constant time. Thus, the initialization of the priority queue adds \(O(|Y|) = O(n)\) to the cost of the initialization.

Lemma 7.24: The initialization of each phase of the Hungarian algorithm takes \(O(n + m)\) time and establishes Invariant 7.23.