Is there any result on approximating a minimum (weighted) bipartite vertex cover? I'm interested in the problem that given a bipartite graph ( probably with weight on its vertex ), find a vertex cover of size (or weight) at most ($1+\epsilon$) of the optimal value. I've been searching on internet and although it seems the problem was quite simple, there's no paper or lecture notes about it. (maybe because everybody know :)).

Can anyone give a link to related work if you know any :D


  • 1
    $\begingroup$ There are quasi-linear time approximation schemes for computing $(1-\epsilon)$-approximate matching, e.g. web.eecs.umich.edu/~pettie/papers/ApproxMWM.pdf $\endgroup$ Commented Apr 18, 2013 at 12:07
  • $\begingroup$ That's a great paper and it was exactly where I came up with the question. $\endgroup$ Commented Apr 20, 2013 at 3:50

1 Answer 1


No need to approximate, we can determine the exact value: see Kőnig's theorem. In particular, this section shows how to use any maximum bipartite matching algorithm to find a minimum vertex cover.

  • $\begingroup$ Thanks, but I'm just interested in how to find a Vertex Cover WITHOUT finding a maximum matching, and get a better running time than bipartite matching algorithm. $\endgroup$ Commented Apr 16, 2013 at 3:04
  • $\begingroup$ I think these problems are well known to be equivalent - anyhow, good luck with improving the algorithm! $\endgroup$
    – domotorp
    Commented Apr 16, 2013 at 14:42
  • 1
    $\begingroup$ There are many descriptions of weighted matching algorithms, see e.g. cs.princeton.edu/~wayne/kleinberg-tardos/… The runningtime is n^3, but can be improved for sparse graphs You should change the problem statement to ask for O(n^2) approximation algorithms. $\endgroup$ Commented Apr 16, 2013 at 14:47

Your Answer

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

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