Destroy weighted edges in a bidirected graph

Question

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.

If there is only one path between any two nodes and you have to disconnect every node from the others, don't you have to remove _all_ the connections? — BlackBear, Nov 06 '12 at 17:05
no, it is enough to remove one edge from each path to destroy the connectivity. The question is how to choose which edges to remove. — paul schlacter, Nov 06 '12 at 17:15
If I understand the question, nodes in K have to be disconnected from each other, but not necessarily from G nodes that are not in K. Is that correct? — Patricia Shanahan, Nov 06 '12 at 18:22

score 2 · Answer 1 · edited May 23 '17 at 12:09

2

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.

edited May 23 '17 at 12:09

Community

1
1

answered Nov 06 '12 at 22:52

Falk Hüffner

4,942
19
25

score 2 · Answer 2 · answered Apr 14 '17 at 17:58

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

Destroy weighted edges in a bidirected graph

2 Answers2