5

I am trying to figure out an algorithm for finding minimum vertex cover of a bipartite graph.

I was thinking about a solution, that reduces the problem to maximum matching in bipartite graph. It's known that it can be found using max flow in networ created from the bip. graph.

Max matching M should determine min. vertex cover C, but I can't cope with choosing the vertices to set C. Let's say bip. graph has parts X, Y and vertices that are endpoints of max matching edges are in set A, those who are not belong to B.

I would say I should choose one vertex for an edge in M to C. Specifically the endpoint of edge e in M that is connected to vertex in set B, else if it is connected only to vertices in A it does not matter. This idea unfortunately doesn't work generally as there can be counterexamples found to my algorithm, since vertices in A can be also connected by other edges than those who are included in M.

Any help would be appriciated.

yrak
  • 61
  • 1
  • 3

1 Answers1

2

Kőnig's theorem proof does exactly that - building a minimum vertex cover from a maximum matching in a bipartite graph.

Let's say you have G = (V, E) a bipartite graph, separated between X and Y.

As you said, first you have to find a maximum matching (which can be achieved with Dinic's algorithm for instance). Let's call M this maximum matching.

Then to construct your minimum vertex cover:

  • Find U the set (possibly empty) of unmatched vertices in X1, ie. not connected to any edge in M
  • Build Z the set or vertices either in U, or connected to U by alternating paths (paths that alternate between edges of M and edges not in M)
  • Then K = (X \ Z) U (Y ∩ Z) is your minimum vertex cover

The Wikipedia article has details about how you can prove K is indeed a minimum vertex cover.

1 Or Y, both are symmetrical

benterris
  • 634
  • 7
  • 15