<p>No need to approximate, we can determine the exact value: see <a href="http://en.wikipedia.org/wiki/K%C3%B6nig%27s_theorem_%28graph_theory%29">Kőnig's theorem</a>. In particular, this <a href="http://en.wikipedia.org/wiki/K%C3%B6nig%27s_theorem_%28graph_theory%29#Algorithm">section</a> shows how to use any maximum bipartite matching algorithm to find a minimum vertex cover. </p>

CC BY-SA 3.0
2013-04-16T03:04:53.783Z
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
CC BY-SA 3.0
2013-04-16T14:42:40.167Z
I think these problems are well known to be equivalent - anyhow, good luck with improving the algorithm!
domotorp
CC BY-SA 3.0
2013-04-16T14:47:18.167Z
There are many descriptions of weighted matching algorithms, see e.g.
http://www.cs.princeton.edu/~wayne/kleinberg-tardos/07AssignmentProblem-2x2.pdf
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
CC BY-SA 3.0
2013-04-15T19:13:48.567Z
2013-04-16T00:40:40.120Z
2013-04-16T00:40:40.120Z
domotorp
<p>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 :)).</p>

<p>Can anyone give a link to related work if you know any :D</p>

<p>thanks</p>

CC BY-SA 3.0
2013-04-18T12:07:30.973Z
There are quasi-linear time approximation schemes for computing $(1-\epsilon)$-approximate matching, e.g. http://web.eecs.umich.edu/~pettie/papers/ApproxMWM.pdf
Markus Bläser
CC BY-SA 3.0
2013-04-20T03:50:19.907Z
That's a great paper and it was exactly where I came up with the question.
Dawei Huang
<graph-theory><approximation>
Approximating Bipartite Vertex Cover
Dawei Huang
# Approximating Bipartite Vertex Cover

(Asked by: username_0 on 2013-04-15)

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

**Tags:** graph-theory, approximation

> **Comments:**
> **username_1**: There are quasi-linear time approximation schemes for computing $(1-\epsilon)$-approximate matching, e.g. http://web.eecs.umich.edu/~pettie/papers/ApproxMWM.pdf  
> **username_0**: That's a great paper and it was exactly where I came up with the question.  

---

## 1 answers

### Answer by username_2 on 2013-04-15. Score: 8

No need to approximate, we can determine the exact value: see [Kőnig's theorem](http://en.wikipedia.org/wiki/K%C3%B6nig%27s_theorem_%28graph_theory%29). In particular, this [section](http://en.wikipedia.org/wiki/K%C3%B6nig%27s_theorem_%28graph_theory%29#Algorithm) shows how to use any maximum bipartite matching algorithm to find a minimum vertex cover.

> **Comments:**
> **username_0**: 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.  
> **username_2**: I think these problems are well known to be equivalent - anyhow, good luck with improving the algorithm!  
> **username_3**: There are many descriptions of weighted matching algorithms, see e.g. http://www.cs.princeton.edu/~wayne/kleinberg-tardos/07AssignmentProblem-2x2.pdf 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.  

---

