Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

From Wikipedia:

König's theorem states that, in bipartite graphs, the maximum matching is equal in size to the minimum vertex cover. Via this result, the minimum vertex cover, maximum independent set, and maximum vertex biclique problems may be solved in polynomial time for bipartite graphs.

König's theorem states about the relation between sizes of the maximum matching and of the minimum vertex cover, not about conversion between any two of the four: the maximum matching, minimum vertex cover, maximum independent set, and maximum vertex biclique. So I wonder how to understand the sentence in bold?

Thanks!

share|improve this question

1 Answer 1

up vote 1 down vote accepted

König's theorem says that two (normally different) problems--min vertex cover and max matching--become the same on bipartite graphs. The wikipedia page for König's theorem gives an example of the conversion. The other two problems are equivalent to these two.

Min vertex cover is trivially the same as max independent set (a set of vertices forms a min cover iff all vertices not in the set are independent; see the wikipedia page for vertex cover for more details).

Every independent set induces a clique in the complement graph (or a biclique in the case of bipartite graphs) so this problem too easily reduces from the others.

share|improve this answer
    
Thanks! (1) I wonder how a independent set induces a biclique in the case of bipartite graphs? (2) Also for conversion between maximum matching and minimum vertex cover, Wikipedia only has one direction, and I feel the description there is not easy to picture, so wonder if there are other more clear sources for the conversions of two directions? –  Tim Nov 2 '12 at 3:32

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.