<p>The weighted vertex cover problem can be formulated as an Integer Program (see <a href="http://en.wikipedia.org/wiki/Vertex_cover">http://en.wikipedia.org/wiki/Vertex_cover</a>). When the input graph is bipartite, the constraint matrix of this IP is totally unimodular. Hence this IP can be solved in polynomial time.</p>

<p>For more details of total unimodular matrices and the corresponding algorithms, see the excellent (three volume) book by <a href="http://rads.stackoverflow.com/amzn/click/3540443894">Alexander Schrijver</a>.</p>

CC BY-SA 3.0
2012-03-23T20:18:53.593Z
To be more precise the IP can be solved by simply solving the LP relaxation. Moreover, one can notice that the dual of the LP is a generalization of matching (with capacities corresponding to weights of the vertices in the vertex cover instance) and can be solved by reducing to maximum flow in the usual way.
Chandra Chekuri
CC BY-SA 3.0
2017-04-08T22:14:01.653Z
@ChandraChekuri peudo-code of the max flow reduction can be found in Figure 4 in [Incremental Computation of Resource-Envelopes in Producer-Consumer Models](https://link.springer.com/chapter/10.1007/978-3-540-45193-8_45)
xuhdev
CC BY-SA 3.0
2012-03-23T03:54:42.580Z
2012-03-23T03:54:42.580Z
Shiva Kintali
<p>I know that for an unweighted bipartite graph, I can find the minimum vertex cover by first finding the maximum matching and turning it into a vertex cover using König's Theorem. Is there a modification one could use if the nodes are weighted?</p>

CC BY-SA 3.0
2012-03-23T16:28:01.220Z
Although the solution given by Shiva Kintali solves your problem, I'd just like to add a quick remark: König's theorem is all about cardinality. You could add weights, finding a min-cost maximum bipartite matching (there are algorithms for this with edge weights; easy to use node weights instead), but you'd still just get the min-cost minimum vertex cover – which might not be the min-cost vertex cover (i.e., that could consist of more nodes). A min-cost matching with no cardinality constraints/optimization would just be empty (for positive weights)…
Magnus Lie Hetland
<ds.algorithms><graph-theory>
What is an algorithm to find a minimum vertex cover on a bipartite graph with weighted vertices?
Andrey Fedorov
# What is an algorithm to find a minimum vertex cover on a bipartite graph with weighted vertices?

(Asked by: username_0 on 2012-03-23)

I know that for an unweighted bipartite graph, I can find the minimum vertex cover by first finding the maximum matching and turning it into a vertex cover using König's Theorem. Is there a modification one could use if the nodes are weighted?

**Tags:** ds.algorithms, graph-theory
> **Comments:**
> **username_1**: Although the solution given by Shiva Kintali solves your problem, I'd just like to add a quick remark: König's theorem is all about cardinality. You could add weights, finding a min-cost maximum bipartite matching (there are algorithms for this with edge weights; easy to use node weights instead), but you'd still just get the min-cost minimum vertex cover – which might not be the min-cost vertex cover (i.e., that could consist of more nodes). A min-cost matching with no cardinality constraints/optimization would just be empty (for positive weights)…  

---

## 1 answers

### Answer by username_2 on 2012-03-23. Score: 18 | Accepted answer

The weighted vertex cover problem can be formulated as an Integer Program (see <http://en.wikipedia.org/wiki/Vertex_cover>). When the input graph is bipartite, the constraint matrix of this IP is totally unimodular. Hence this IP can be solved in polynomial time.

For more details of total unimodular matrices and the corresponding algorithms, see the excellent (three volume) book by [Alexander Schrijver](http://rads.stackoverflow.com/amzn/click/3540443894).

> **Comments:**
> **username_3**: To be more precise the IP can be solved by simply solving the LP relaxation. Moreover, one can notice that the dual of the LP is a generalization of matching (with capacities corresponding to weights of the vertices in the vertex cover instance) and can be solved by reducing to maximum flow in the usual way.  
> **username_4**: @ChandraChekuri peudo-code of the max flow reduction can be found in Figure 4 in [Incremental Computation of Resource-Envelopes in Producer-Consumer Models](https://link.springer.com/chapter/10.1007/978-3-540-45193-8_45)  

---

