The Vertex Cover of a graph $G(V,E)$ is a set of vertices $S \subseteq V$ such that each edge of the graph is incident to at least one vertex of the set $S$.
Minimum cost vertex cover : Given a graph $G(V,E)$ and a cost function on the vertex set $V$, find a minimum cost vertex cover in $G$.
Formulate Minimum cost vertex cover as an integer program (IP).
When $G$ is a bipartite graph, prove that the constraint matrix of this IP is totally unimodular. Hence conclude that the natural linear programming relaxation of this IP is integral, implying that Minimum Weighted vertex cover is polynomially solvable on bipartite graphs.
Posted: Sep 11 '12
Seen: 116 times
Last updated: Sep 11 '12
