Minimum damaging costs in graph

Question

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!

Answer 1

I think a modified Kruskal is the way to go here.

Take the graph G'=(V', E'), V'=V, E'={}. Sort the edges in E in non-increasing order of cost. Now, for each edge in E, add it to E' iff it does not connect two components that both have vertices with bombs in them. The result is the sum of the costs of E-E'.

EDIT:

Running this on your example.

Initially, our set of edges is empty {}, and we take the edges sorted in non-increasing order [(1, 2), (0, 1), (2, 4), (1, 3)]

So, at the start, our graph is made up of 5 disconnected components.

(1, 2) has a cost of 8, and only one of the components it connects has a bomb. So we add it to E'. E'={(1, 2)} and we have 4 components.

The next highest cost edge is (0, 1) with a cost of 5. But both components have bombs, so don't add this edge.

The next one is (2, 4). This also connects to components with bombs, so we skip this as well.

Lastly the lowest cost edge is (1, 3). Since one of its components (containing just the node 3) does not have a bomb, we add it to E'.

This gives us E' = {(1,2), (1, 3)}.

My reasoning is that we try adding edges with higher cost before ones with lower cost - which ensures that in any path between nodes with bombs in the original node, all but the lowest cost will be added.