5
$\begingroup$

Vertex cover in bipartite graph is polynomial algorithm: by König's theorem the number of edges in a maximum matching is the number of vertices in a minimum vertex cover. I've implementated the Hopcroft Karp algorithm to find a maximum matching in the bipartite graph. I would like to get the minimum vertex cover from this.

Is there any way of adjusting Hopcroft–Karp so that it produces the minimum vertex cover, other than the obvious way of just computing the matching and then passing that to an algorithm that computes the corresponding cover?

Improve this question
$\endgroup$
0

3 Answers 3

Reset to default
5
$\begingroup$

The Wikipedia page on König's theorem gives an algorithm that converts a maximum matching to a minimum vertex cover. I'm not sure that an algorithm for finding maximum matching can be tweaked to an algorithm for finding minimum vertex cover in any other way, though it's perfectly possible.

Improve this answer
$\endgroup$
1
  • $\begingroup$ you are correct.I wrote an answer. $\endgroup$
    – Manoharsinh Rana
    Apr 21, 2019 at 18:39
2
$\begingroup$

Hopcroft–Karp fundamentally uses the fact that it's computing a matching. If you try to compute the vertex cover straight away by storing just the vertices in the cover constructed so far, the concept of "alternating path" makes no sense because it's defined with respect to a set of edges, not vertices. So it seems unlikely that there's a "Hopcroft–Karp-like" algorithm for min vertex cover that isn't just Hopcroft–Karp followed by a transformation from the matching to the cover.

(Well, I suppose you could try to construct the cover as you went along, updating it every time the matching is updated. But that's not fundamentally different and I don't see how it would be more efficient.)

Improve this answer
$\endgroup$
1
$\begingroup$

This is the way.

Suppose you have left and right parts in bipartite graph and you found the maximum matching M.

Let's define orientation of edges. Those edges that belong to M will go from right to left, all other edges will go from left to right.

Now run DFS starting at all left vertices that are not incident to edges in M. Some vertices of the graph will become visited during this DFS and some not-visited.

To get minimum vertex cover you take all visited right vertices of M, and all not-visited left vertices of M.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.