Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

svg_af's blog

Help with minimum vertex cover in bipartite graphs
By svg_af, history, 10 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

»
10 years ago, hide # |
 
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