Associate each node of an undirected graph with positive weight. The vertex packing problem is to find a subset of the nodes with the largest sum of weights, such that no two nodes with an edge between them are chosen.
What is the most efficient way of solving the vertex packing problem for a bipartite graph? I have been able to formulate it as a maximum flow problem with twice the number of nodes. Is there a more efficient, possibly direct, approach?
Well, P is a feasible solution for the vertex packing problem iff V-P is a feasible solution for the vertex cover problem. Thus a maximum vertex packing is equivalent to a minimum vertex cover. The minimum vertex cover is in turn equivalent to the maximum matching for bipartite graphs.