CODEWITHSUNDEEP
algorithmgraphtree
Paresh
Paresh

Reputation: 552

Min cost edge deletions in tree to separate all leaves in a tree

This is from a larger problem, that I have boiled down to the following problem. Given a weighted tree with positive edge weights, and having k leaves. A leaf is a node which has exactly one adjacent node in the tree. I need to delete some edges from the tree so that the tree splits up into k components, with each component containing exactly one of the leaf nodes from the original tree. In other words, I need to delete edges so that all the leaves in the original tree are separated/disconnected from every other leaf of the original tree.

I need to do this in such a way that the sum of weights (cost) of the deleted edges is minimized. It is trivial to show that k-1 edges need to be deleted. So I need to minimize the sum of weights of these k-1 edges.

What is the optimal way to do this? Any hints would be appreciated. Thanks!

Upvotes: 4

Views: 729

Answers (1)

Peter de Rivaz
Peter de Rivaz

Reputation: 33509

I think a greedy algorithm works here.

i.e. delete the lowest weight edge that generates a new component and repeat k-1 times.

Note that you have to be careful for a graph such as:

D<-A->B->C

If you delete B->C first, then deleting A->B does not generate a new component because B was not a leaf so does not need to be separated.

In other words, when selecting the lowest weight edge, do not include any edges that do not still lead to a leaf node.

Upvotes: 1

Related Questions