HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Vertex cover in bipartite graph from Hopcroft-Karp Algorithm

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
fromgraphhopcroftvertexbipartitealgorithmcoverkarp

Problem

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?

Solution

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.

Context

StackExchange Computer Science Q#33015, answer score: 5

Revisions (0)

No revisions yet.