# Approximating Bipartite Vertex Cover

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

thanks

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

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.

• 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. – Dawei Huang Apr 16 '13 at 3:04
• I think these problems are well known to be equivalent - anyhow, good luck with improving the algorithm! – domotorp Apr 16 '13 at 14:42
• 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. – Martin Vatshelle Apr 16 '13 at 14:47