Find the shortest sub-tree with node deletion

Question

Let $T=(V,E)$ be a tree rooted in $r$ and let $L$ denotes the set of leaves of $T$. For a given $v \in V$, let $C(v)$ be the out-neighors of $v$ i.e. its children in $T$ and $p(v)$ be its in-neighbor i.e. its predecessor in $T$. We have a metric $d : V \times V \rightarrow \mathbb{R}^+$ (respecting the triangular inequality). The length of the tree is then $\sum_{u \in V} d(u,p(u))$.

For a subset of internal non-root nodes $V' \in V \setminus (L \cup \{r\})$, the rooted "sub-tree" $T'$ corresponds to the tree we get after removing each $v\in V'$ and connecting its parent $p(v)$ to all $C(v)$. An example:

My problem is to find the subset of internal $V'$ to remove such that the sub-tree $T'$ has the minimum length. Below are some observations I made (maybe the problem is well-known but if it's not then they may provide some insight). Any remark/reference is most welcome!

Steiner tree related problem?

My first thought was that this problem is a special case of the Steiner tree problem. We can construct a graph $G=(V,A,d)$ with $A = \{(u,v) \in V \times V : u \text{ is an ancestor of } v \text{ in } T\}$, edge length $d$ and $L$ as the set of terminal nodes. However a Steiner tree of $G$ may correspond to solutions that are impossible to get via node removal on $T$. Indeed, node removal preserves the siblings relations existing in $T$. This may not the the case for Steiner trees in G.

That being said I would be interested to know the complexity of the Steiner tree problem for graphs constructed like G. I suspect the problem to still be NP-hard. Note that the approximate solution obtained by taking a minimum spanning tree according to shortest-paths distances would be the star graph connecting the terminal nodes to $r$ (since $d$ respects the triangular inequality).

Iterative/Recursive solution or approximation?

Assuming $T$ is of height $2$, we only need to check if each internal node $u$ respects the inequality

\begin{equation} \sum_{l \in C(u)} d(l,r) > d(u,r) + \sum_{l \in C(u)} d(l,u) \text{ (Ineq. 1)} \end{equation}

and add it to $V'$ if it does not. In the general case, a possible approach is therefore to iteratively remove the nodes that do not respect the Ineq. 1. However, such "local" approach may lead to the best solution. For example assume the distances $d$ for the example in Figure 1 are (sorry for the formatting):

   d(.,.) | r | a | b | l_(1,2,3) | l_4 | l_5 |
   ____________________________________________
   r      | 0 | 2 | 2 | 1         | 3   |   1 |
   a      |   | 0 | 1 | 2         | 1   |     |
   b      |   |   | 0 | 1         |     |     |

Here Ineq. 1 is respected for both internal node $a$ and $b$. However, the shortest tree is the one obtained after the removal of both nodes.

I therefore tried to apply Ineq. 1 in a recursive fashion. I check it not only for the direct parent but for all the ancestors. The procedure is as follow:

Procedure ShortestSubTree$(T,u,d)$:

1. For $v \in C(u) \setminus L$ do
   • ShortestSubTree$(T,v,d)$
2. $a \leftarrow p(u)$
3. While $a$ is defined do
   1. If $\sum_{v \in C(u)} d(a,v) \leq d(u,a) + \sum_{v \in C(u)} d(u,v)$ then
      • remove $u$ from $T$
      • stop
   2. $a \leftarrow p(a)$

However it seems that ShortestSubTree removes too many nodes. In some experiment, the "iterative" approach can produce shorter sub-trees.

Answer 1

This can be solved with dynamic programming.

Define $A[u,v]$ as follows. Consider all trees obtainable by starting with the subtree rooted at $v$, removing some of the nodes, and making $u$ be the parent of all of the nodes with no parent. (Or, to put it another way: all of these trees are a subset of the subtree rooted at $u$; they contain $u$ as their root; and every node in them other than $u$ is either $v$ or a descendant of $v$.) Then $A[u,v]$ is defined to be the length of the minimal-length tree of this sort.

Notice that we have a recursive relationship for $A[u,v]$. In particular, if $w_1,\dots,w_k$ denote the children of $v$, then we have

$$A[u,v] = \min(d(u,v) + A[v,w_1] + \dots + A[v,w_k], A[u,w_1] + \dots + A[u,w_k]).$$

(Here the first term in the $\min$ corresponds to the case where $v$ is included in the tree, and the second term where $v$ is not included.)

As a result, we can compute all of the $A[u,v]$ values using dynamic programming. There are at most $O(|V|^2)$ many values to compute, and each one can be computed in $O(k)$ time where $k$ is the maximum degree of the tree, so the total running time is $O(|V|^2 k)$.