3
$\begingroup$

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:

enter image description here

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.

$\endgroup$
  • $\begingroup$ Have you tried applying dynamic programming? $\endgroup$ – D.W. Jul 5 '18 at 15:28
  • $\begingroup$ To be honest, I am not very familiar with the subject so I do not really know where to begin. If I understand correctly the idea is to separate the problem into smaller problems recursively and being able to combine smaller solutions. The issue here is the combination in my opinion: if I focus on a part of the tree, I still need to take into account the distance from its nodes to the higher part of the tree. $\endgroup$ – fqueyroi Jul 5 '18 at 16:22
  • $\begingroup$ OK, take a look at cs.stackexchange.com/tags/dynamic-programming/info to learn more about dynamic programming. (What's the context where you encountered this problem, or the motivation?) $\endgroup$ – D.W. Jul 5 '18 at 17:23
  • $\begingroup$ Thanks for the link! I will try to use this approach and come back if I have something. For the context: The idea is to "prune" a dendogram obtained via Hierarchical clustering of a set of points in a metric space. The objective is to produce a smaller hierarchy that still contains important features. $\endgroup$ – fqueyroi Jul 6 '18 at 7:27
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks you very much! While trying to formulate (thanks to your refs to dynamic programming) the minimum length recursively I came to something close. I implemented it and this works well (we also need to keep track of the nodes that need to be removed but it is quite straightforward). In my application the tree lengths found using dynamic programming are actually close to the one we get with the iterative method described in my question. $\endgroup$ – fqueyroi Jul 6 '18 at 18:04

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.