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!
Best Answer
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.