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?
$\begingroup$
$\endgroup$
1
-
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$– Magnus Lie HetlandMar 23, 2012 at 16:28
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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$ 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$– xuhdevApr 8, 2017 at 22:14