Minimum damaging costs in graph
algorithm, graph, multiway-tree
Solution
This is the Multiway Cut problem in trees. 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.
Problem
We are given a graph G(V,E) with N nodes (Numbered from 0 to N-1) and exactly (N-1) two-way Edges. Each edge in a graph has a positive cost C(u,v)(Edge weight). The entire graph is such that there is a unique path between any pair of Nodes. We are also given a List L of node number,at which bomb are placed. Our aim is to damage/remove the edge from the graph such ,that after damaging/removing the edges from the graph ,there is no connection among the Bombs -- that is after damaging, there is no path between any two bombs. The cost of damaging the Edge(u,v) = Edge weight(u,v). So, we have to damage those edges, such that the total damaging cost is minimum. Example: ``` Total Nodes=N=5 Total Bomb=Size of List L=3 List L={2,4,0}//Thats is at node number 2,4 and 0 bomb is placed... Total Edges =N-1=4 edges are:: u v Edge-Weight 2 1 8 1 0 5 2 4 5 1 3 4 In this case the answer is :: Total Damaging cost =(Edge Weight (2,4) + Edge Weight(0,1)) =5+5=10. So when we remove the edge connecting node (2,4), and the edge connecting node (0,1) ,there is no connection left between any pair of machines in List {2,4,0}; Note any other,combinations of edges(that we damaged ) to achieve the target goal ,needs more than 10 unit cost. ``` ``` Constraints:: N(ie. Number of Nodes) <= 100,000 ListSize |L|(ie. Number of Bombs) <= N 1 <=Edge cost(u,v) <= 1000,000 ``` What i had done? Until now, I had not found any efficient way :( . Further, as the number of nodes is `N`, the number of edges is exactly `N-1` and the entire graph is such there is a Unique path between any pair of Nodes, I got a conclusion that the graph is a TREE. I tried to modify the Kruskal algorithm but that didn't help me either. Thanks!