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?
5
votes
How is your graph represented? Where are the weights? At the edges or at the nodes? What do you mean by independent vertex set?
– Nico Schertler
It doesnt matter how the graph is represented. Each vertex has some integer weight. You may read about independent set here - en.wikipedia.org/wiki/Independent_set_(graph_theory)
– juver
For the general graph this problem known to be NP-complete. But for the bipartite graph does the same approaches?
– juver
Yes it's possible using min cut
– Niklas B.
@NiklasB. Could you describe the idea please?
– juver
2 Answers
17
votes
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.
-1
votes
It doesnt seem to me that this question is well posed. For one thing, a bi partite graph is already made up of two independent sets. Any independent sets must be subsets of these sets, and for positive weights they trivially must have lower weight?
Splitting up a bipartite graph into disconected sub sets is trivial also, and for most practical purposes, a bipartite graph will have few of these disconnected subsets, so you could just add them up. Since you can find all independent subsets in linear time, and you can find their weight in linear time, it seems obvious that you can do this in linear time in Nodes+edges,
Which makes me suspect that somehoe I have misintepreted your question.
Basically, start with your bipartite graph, select a node, find all nodes that are connected to it. If this is not the whole graph, you have found a disconnected subset, Rinse and repeat. You can add up as you go, so the whole think takes a constant time operation for every Node and Edge = linear time in N+E.
