svg_af's blog

Help with minimum vertex cover in bipartite graphs
By svg_af, history, 9 years ago, In English

Hello there

I know that minimum vertex cover is equal to maximum matching

My question is about how to find the vertices that form the cover

any help would be appreciated

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Let X-Y be a bipartition of the vertex set.

  • Find a Maximum Matching (Theorem: A matching is maximum iff there isn't any augmenting path).
  • Call U the set of unsaturated vertices of X.
  • Call Z the set of vertices reachable from U (including U itself) through an alternating path.
  • Make (Latex seems to be broken, I wrote: R = (X-Z) union (Y intersection Z) )

R is a minimum cover.

It's fairly easy to prove it, but this is essentially König's theorem's proof, check it out in wikipedia.

→ Reply