König's Theorem (graph Theory) - Algorithm

Algorithm

Consider a bipartite graph where the vertices are partitioned into left and right sets. Suppose there is a maximum matching which partitions the edges into those used in the matching and those not . Let consist of all unmatched vertices from L, as well as all vertices reachable from those by going left-to-right along edges from and right-to-left along edges from . This essentially means that for each unmatched vertex in L, we add into T all vertices that occur in a path alternating between edges from and .

Then is a minimum vertex cover. Intuitively, vertices in are added if they are in and subtracted if they are in to obtain the minimum vertex cover. Thus, the Hopcroft–Karp algorithm for finding maximum matchings in bipartite graphs may also be used to solve the vertex cover problem efficiently in these graphs.

Despite the equivalence of the two problems from the point of view of exact solutions, they are not equivalent for approximation algorithms. Bipartite maximum matchings can be approximated arbitrarily accurately in constant time by distributed algorithms, but in contrast approximating the minimum vertex cover of a bipartite graph requires at least logarithmic time.