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

Improve this question
$\endgroup$
2
  • 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, 2013 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, 2013 at 3:50

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
3
  • $\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, 2013 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, 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$
    – Martin Vatshelle
    Apr 16, 2013 at 14:47

Your Answer

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

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