3
$\begingroup$

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!

$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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? $\endgroup$
    – Tim
    Nov 2, 2012 at 3:32

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.