Maximum weighted independent set in bipartite graph

Question

Given bipartite graph. Each vertex has some integer value - weight.

Is it possible to find maximum weighted independent vertex set in this graph in polynomial time?

If such solution exists, what is the algorithm for this problem?

Answer 1

In any graph, the complement of an independent set is a vertex cover and vice versa, so your problem is equivalent to finding the minimum weight vertex cover in the graph. The latter can be solved using maximum flow techniques:

Introduce a super-source S and a super-sink T. connect the nodes on the left side of the bipartite graph to S, via edges that have their weight as capacity. Do the same thing for the right side and sink T. Assign infinite capacity to the edges of the original graph.

Now find the minimum S-T cut in the constructed network. The value of the cut is the weight of the minimum vertex cover. To see why this is true, think about the cut edges: They can't be the original edges, because those have infinite capacity. If a left-side edge is cut, this corresponds to taking the corresponding left-side node into the vertex cover. If we do not cut a left-side edge, we need to cut all the right-side edges from adjacent vertices on the right side.

Thus, to actually reconstruct the vertex cover, just collect all the vertices that are adjacent to cut edges, or alternatively, the left-side nodes not reachable from S and the right-side nodes reachable from S.