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?

  • 1
    $\begingroup$ 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)… $\endgroup$ Commented Mar 23, 2012 at 16:28

1 Answer 1


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.

  • 6
    $\begingroup$ 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. $\endgroup$ Commented Mar 23, 2012 at 20:18
  • $\begingroup$ @ChandraChekuri peudo-code of the max flow reduction can be found in Figure 4 in Incremental Computation of Resource-Envelopes in Producer-Consumer Models $\endgroup$
    – xuhdev
    Commented Apr 8, 2017 at 22:14

Your Answer

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

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