Menu
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?
550
A maximum independent line set of 'G' with maximum number of edges is called a maximum independent line set of 'G'. L3 is the maximum independent line set of G with maximum edges which are not the adjacent edges in graph and is denoted by β1 = 3. Line independent number (Matching number) = β1 = [n/2] α1 + β1 = n.
The Maximum Independent Set (MIS) problem in graph theory is the task of finding the largest independent set in a graph, where an independent set is a set of vertices such that no two vertices are adjacent. There is currently no known efficient algorithm to find maximum independent sets.
Although the result is not explicitly stated in their paper, Hearn and Demaine [12] first proved that the reconfiguration of independent sets is PSPACE-complete, both under the TJ and the TS model.
1 Answer. Show activity on this post. The maximum size of the independent set in this tree is 10. This can be obtained by the following dynamic programming over tree: for each vertex, we will calculate the maximum independent set of a subtree of this vertex with this vertex included and without.
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.
93
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
