CODEWITHSUNDEEP
algorithmgraph-theorydynamic-programming
paul schlacter
paul schlacter

Reputation: 195

Destroy weighted edges in a bidirected graph

On my recent interview I was asked the following question: There is a bidirectional graph G with no cycles. Each edge has some weight. Also there is a set of nodes K which should be disconnected from each other (by removing some edges). There is only one path between any two nodes in K set. The goal is to minimize total weight of removed edges and disconnect all nodes (from set K) from each other.

My approach was to run BFS for each node from K set and determine all paths between all pairs of nodes from K. So then I'll have set of paths (each path is a set of edges). My next step is to apply dynamic programming approach to find minimum total weight of removed edges. And here I stuck. Could you please help me (just direct me) of how DP should be done.

Thanks.

Upvotes: 2

Views: 715

Answers (2)

KARTHEEK REDDY
KARTHEEK REDDY

Reputation: 21

This problem can be solved using disjoint Sets. In this problem you need to make set of each vertex like forest. Then, join the vertices which belong to two different sets through the edges which are in the graph such that -

1) if one of the set contains a node which is mentioned in the k set of nodes, then the node becomes the representative element.

2) if both the sets contain the unwanted node (node present in the k set of nodes), then find the minimum weight edge in both the sets and compare them, then compare the minimum one of them with the edge to be joined and find the minimum. Then delete the edge which we found so that no path exists b/w them.

3) if none of the set contain the unwanted node, then join one set to the other set.

In this way you find the minimum total weight of the destroyed edges in a very good time complexity of the order of O(nlogn). Your approach will also work but it will prove to be costly in terms of time complexity.

Here is the complete code - (GameAlgorithm.cpp) https://github.com/KARTHEEKCIC/RoboAttack

Upvotes: 2

Falk Hüffner
Falk Hüffner

Reputation: 5040

This sounds like the Multiway Cut problem in trees, assuming a "bidirectional" graph is just like an undirected one. It can be solved in polynomial time by a straightforward dynamic programming. See Chopra and Rao: "On the multiway cut polyhedron", Networks 21(1):51–89, 1991. See also this question.

Upvotes: 2

Related Questions