Choose minimum subset of edges in tree that connects all important nodes

Question

Let's say we have given weighted tree of size $n$ and list of important nodes in the tree $k$.

We want to choose subset of edges of the tree such that:

• For each two important nodes at least one edge of the path between them will be choosen
• The sum of the subset of edges will be minimized

Note that we only need to find the sum of the edges in the subset, not the edges in the subset.

For example if we have the tree with the edges $(1, 2) \text{ weight = 3}, (1,3) \text{ weight = 10}$ And our important nodes are: $2, 3$. We should chose only the edge $(1,2)$

Answer 1

Note this is equivalently finding edges with minimum sum of weights such that their removal leaves each important node in a separate component, which is called minimum multiway cut problem.

This problem is NP-hard in general graph, while Chopra, Sunil, and Mendu R. Rao developed a polynomial time algorithm for tree in 1991 [1].

---

_{[1] Chopra, Sunil, and Mendu R. Rao. "On the multiway cut polyhedron." Networks 21.1 (1991): 51-89.}