4
$\begingroup$

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

$\endgroup$
  • 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$ – Markus Bläser Apr 18 '13 at 12:07
  • $\begingroup$ That's a great paper and it was exactly where I came up with the question. $\endgroup$ – Dawei Huang Apr 20 '13 at 3:50
8
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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