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)$


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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.