3
$\begingroup$

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.

Kuhn-Munkres Algorithm

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?

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ Please copy the text from the picture here, so it can be searched for $\endgroup$ – Raphael♦ Dec 12 '12 at 20:25
  • 1
    $\begingroup$ 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. $\endgroup$ – Isaac Kleinman Dec 13 '12 at 15:39
  • 1
    $\begingroup$ 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. $\endgroup$ – Raphael♦ Dec 13 '12 at 20:02
  • 1
    $\begingroup$ you fail to address my main point that anything anyone would search for is NOT embedded in the image, so unless someone does a search for mathematical jargon, I think they'll be fine. $\endgroup$ – Isaac Kleinman Dec 14 '12 at 15:32
  • 1
    $\begingroup$ I think this discussion is going on for longer than it should, but take a look at the image: subtract all words that appear as text in my question; also, subtract all mathematical markup since that's not searchable anyway. Now, what words are left, 'choose', 'find', 'otherwise'. Do we really have to accommodate someone searching for those terms? $\endgroup$ – Isaac Kleinman Dec 19 '12 at 18:14
3
$\begingroup$

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.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.