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!

Nonconformance

I believe a greedy approach (remove the lowest vertex in each path) has a chance in a tree, but am not sure about it yet :\ Also: What would you find as an efficient approach? – Papist

@amit,Till now i am not too able to find any efficient method ,to solve this.The constraint Number of Nodes =100,000 ,that means total edges =100,000-1. So O(n log n) algorithm will be handy and efficient. – Nonconformance

@All:: Added the constraints as an Edit. – Nonconformance

If graph is fully connected it's tree, but otherwise it can be normal graph. – Galbraith

Answer 1

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.

Fairminded

Nice answer, IMO it's better to provide multiway cut definition. – Galbraith

cs.ust.hk/mjg_lib/Classes/COMP572_Fall06/Notes/Tree_Multicut.ps has a description of the algorithm. google.com/… – Presidentship

Answer 2

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.

Sheltonshelty

MaK ,Can you please give an example.I don't think this approach works as there is always ONE connected components since "The entire graph is such there is a Unique path between any pair of Nodes".Please correct me if i am wrong,i think if u can illustrate ur approach ,taking the sample input as example,then it will be much easier to understand. – Nonconformance

Answer 3

I think this can be done in linear time.

Root the tree in some vertex and then start with bottom-up traversal.

Start with some leaf. If there is no bomb, cut off the leaf and move along. If there is a bomb you have to cut one edge on a path to this leaf. Propagate information about cheapest edge to this leaf up.

Then when you are in inner vertex, you have this possibilities: If there is a bomb in vertex and some bombs below, cut cheapest paths to all of them. If there is no bomb and only one bomb below, propagate information about cheapest path. If there are more bombs below, cut every one except one with the most expensive path.

Magnusson

I was thinking the same way, but couldn't come to a final algorithm, your idea with remembering subtrees that are equivalent to one bomb does it, I think. – Celery

Answer 4

Here is my hypothesis:

The Graph G is a tree. Hence there is only one path between any two nodes.

Suppose there are L Red (Bomb) nodes and V-L White (non-Bomb nodes). The solution requires the partition of G into a forest of L sub-trees. This requires the removal of a minimum of L-1 edges.

Each of the edged removed has to be on a path between two Red nodes.

A. Prune the tree G to remove all edges which do not participate in a path between two red nodes.

1. Remove White leaf nodes (and the incident edge) from consideration.
2. Repeat #1 until there are no White leaf nodes in the modified graph.

B. After (A) all the edges left in the graph are edges which form a path between two red nodes.

Select the edge with the lowest weight in this tree. This will result in two sub-trees with each tree containing at least one Red node.

C. Go back to Step A for each of the sub-trees created in B if it contains more than one Red Node.

This is O(V log V) (|E| is |V| -1 ).

Presidentship

Answer 5

I think the following suggestion should work:

• 1) Start with a bomb, in your example I start with: 0
• 2) Create paths witch all adjacent nodes. So take all relationships and start a path with them. In your example it will start one path: 0 -> 1.
• 3) If you hit another bomb on a path, you remove the edge with the lowest cost. In the example we don't hit a bomb, so we continue with step2.
• 3A)No bomb in any path yet. Continue with step 2 and extend the paths with the new adjacent nodes. In your case a new path will be created: 1 -> 3. And the existing one will be extended: 0 -> 1 -> 2
• 3B)A bomb is found on the path. Take the path where the bomb is found, and remove the edge with the lowest cost. In your example the path 0 -> 1 -> 2 contains a bomb (2). So we remove the relationship with cost 5. Remove the path from the 'todo' and continue with step 2 on the last reached nodes (2 and 3).

I the end you should traverse each node exactly once. If I am not mistaken the complexity should be about O(n log n)

Heretic

Answer 6

http://www.cs.ust.hk/mjg_lib/Classes/COMP572_Fall06/Notes/Tree_Multicut.ps

has a description of the algorithm.

Google HTML version of the postscript file

=========================================

http://dspace.mit.edu/bitstream/handle/1721.1/5394/OR-308-95.pdf?sequence=1

The case k = 2 is not the only polynomially solvable instance of the multiway cut problem. Lovdsz [12] and Cherkasskij [3] show that when ce = 1 Ve E E and G is Eulerian, then the multiway cut problem is polynomially solvable. Erdos and Sz6kely [8] have shown that a generalization of the multiway cut problem is polynomially solvable when the underlying graph G is a tree. Dalhaus et. al. [7] have shown the problem to be polynomial solvable for fixed k on planar graphs.

I had written a simple greedy algorithm based solution last night which consisted of removing nodes which are not on a path between two red (Terminal) nodes, and then selecting the smallest weight node, and then repeating the process on the sub-trees. I deleted that since further reading suggested that the problem is NP. But this reference suggests that there is an polynomial solution...

Presidentship