# Clarification with Kuhn-Munkres/Hungarian Algorithm

I have been attempting to get my mind around the Kuhn-Munkres/Hungarian Algorithm. I have been using the following statement of the algorithm which I found here.

Based on my readings on the algorithm, my understanding is that the improvement of the feasible vertex labeling in step 2. is supposed to be such that $G_l \subset G_l'$.

The part I'm getting stuck on is that it seems to me that it is possible for there to be an edge $xy$ in $G_l$ with $y \in T$ but $x \not \in S$ resulting in the fact that $$l'(x) + l'(y) = l(x) + (l(y) + \alpha_l) \not = w(xy)$$ and so $xy \not \in G_l'$ and $G_l \not \subset G_l'$.

Can anyone point out where I'm going wrong?

-
Please copy the text from the picture here, so it can be searched for – Raphael Dec 12 '12 at 20:25
How do you copy formatted text from a pdf? – Isaac Kleinman Dec 12 '12 at 20:34
There are tools like pdftotext, but I meant transcribing it yourself. – Raphael Dec 13 '12 at 9:08
Mere transcribing wouldn't do the trick, it would need quite a bit of mathjaxing which I'm not really up for. But that's beside the point, any potentially searchable 'buzzwords' appear in the body of the question as text. – Isaac Kleinman Dec 13 '12 at 15:39
I'm afraid "I don't want to" is not an option here. Posts whose content is buried in images are generally bad form, to the point of being deletion-worthy (see here, here). Therefore, you should really invest the work (what's the message if you don't?). See here for a primer on how to use maths here. – Raphael Dec 13 '12 at 20:02

You are right that $G_{l'}$ is not necessarily a superset of $G_l$. However, you can still prove that the algorithm runs in strongly polynomial time. You have the following invariants:
• all edges in $M$ remain edges of $G_{l'}$
• we don't remove vertices from $S$ and $T$ until we increase the size of the matching $M$, at which point $S$ and $T$ are reset (step 1); so the size of $S$ and $T$ is monotonically increasing until the size of $M$ is increased by 1
• after updating the labels to $l'$, the size of $T$ is increased by at least 1 in the next step
What can you conclude from this? The size of the matching $M$ never decreases. At each iteration we either increase the size of $T$, or we update the labels, which will cause us to increase the size of $T$ in the next iteration. So after $2n$ iterations, the size of $T$ will be $n$. Since $T$ cannot grow anymore, we will have to increase the size of $M$. But the size of $M$ is at most $n$, so the algorithm will finish after at most $O(n^2)$ iterations. An iteration can be executed in time $O(m)$, so the total running time is bounded by $O(n^2m)$.
BTW the sets $S$ and $T$ are a bit mysterious in this description of the algorithm. Here is how we usually think about them. Orient all edges in $G_l$ as follows: the edges in $M$ go from $Y$ to $X$ and all other edges go from $X$ to $Y$. Then $x$ is an unmatched vertex, $T$ is computed to be the set of vertices in $Y$ reachable from $x$ by a directed path, and $S$ is the set of vertices in $X$ reachable from $x$ by a directed path. If $T$ contains an unmatched vertex, we have found an odd-length alternating path, and we can augment the matching (increase its size by reversing the direction of the edges along the path). Otherwise, we can change $l$ so that the size of $T$ increases.