Relations between the maximum matching, minimum vertex cover, maximum independent set, and maximum vertex biclique for a bipartite graph

16.7k Views Asked by At

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!

1

There are 1 best solutions below

1
On 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.