Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
1  
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
1  
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
show 3 more comments

1 Answer

up vote 3 down vote accepted

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.

share|improve this answer
    
The source of my error was page 11 of this presentation cse.ust.hk/~golin/COMP572/Notes/Matching.pdf which states that the equality subgraph of the original labeling is a subgraph of the new equality subgraph. I found Wikipedia's entry much more accurate and helpful: en.wikipedia.org/wiki/Hungarian_algorithm –  Isaac Kleinman Dec 18 '12 at 15:31
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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