6
$\begingroup$

Given a tree $T$, I want to find a subset $N$ of $n$ leaves that are farthest apart. I.e., I want to find $N$ that maximizes function:

$$f(N)=\sum\limits_{x_1,x_2 \in N, x_1 \neq x_2}{dist(x_1,x_2)}$$

where $dist(x_1, x_2)$ is the number of edges in a path between two vertices/nodes $x_1$ and $x_2$.

What algorithm can I use?

$\endgroup$
0
3
$\begingroup$

If you have a binary tree, you should be able to solve this using dynamic programming.

Let $A[v,j,k]$ denote the maximum possible value of the objective function

$$f'(N) = \sum_{x_1,x_2 \in N} \text{dist}(x_1,x_2) + k \sum_{x \in N} \text{dist}(v,x)$$

where $N$ ranges over all subsets of exactly $j$ leaves from among those that are descendants of $v$ (i.e., leaves of the subtree rooted at $v$).

If $v$ is a leaf, it is easy to compute $A[v,j,k]$ for all $j,k$.

If $v$ has one child $v'$, it is easy to compute $A[v,j,k]$ for all $j,k$ from $A[v',\cdot,\cdot]$.

So now suppose $v$ has two children $v',v''$. Then we can work out a recursive equation for $A[v,j,k]$ in terms of values $A[w,\cdot,\cdot]$ where the $w$'s are descendants of $v$:

$$A[v,j,k] = \max A[v',j',k+j''] + A[v'',j'',k+j'] + 2 j' j'' + jk$$

where $j',j''$ range over all values such that $j'+j'' = j$, $0 \le j',j'' \le j$. The intended meaning is that $j'$ counts the number of leaves in $N$ that are descendants of $v'$ and $j''$ counts the number of leaves in $N$ that are descendants of $v''$. In other words, we split $N=N' \cup N''$ where $N'$ contains $j'$ leaves from the descendants of $v'$, and $N''$ contains $j''$ leaves from the descendants of $v''$; then (loosely speaking) we compute the maximum value of $f'(N)$ in terms of the maximum values of $f'(N')$ and $f'(N'')$. The $2jj'$ term counts distances of the form $\text{dist}(x_1,x_2)$ where $x_1 \in N'$ and $x_2 \in N''$. The $jk$ term accounts for the fact that the $j$ root-to-leaf paths all need to be extended by one edge (thank you @j_random_hacker).


If you have an arbitrary tree (not necessarily a binary tree), you can convert it to a binary tree as follows: whenever you have a node $v$ with $m$ children, create a little binary tree with $m$ leaves, then put $v$ at the root of that binary tree and paste the children of $v'$ in at its $m$ leaves. Put a distance of 0 on all the edges of that new little binary tree except the top level. Repeat recursively.

In this way you obtain a binary tree where every edge has a distance of either 0 or 1 on it, and the distance between two vertices $v,w$ is the sum of the distances on the edges in the path between $v$ and $w$. Now you should be able to generalize the above algorithm to that case. I'll let you handle the details.

$\endgroup$
5
  • 1
    $\begingroup$ @dzieciou, Thank you, those are excellent points, my answer had some errors in it. See revised answer. Please review carefully; it might well have other errors as well. $\endgroup$ – D.W. Jan 17 at 20:39
  • 1
    $\begingroup$ Nice approach! I think that there needs to be an additional $jk$ term in the recursion formula though, to account for the fact that the $j$ leaf-to-$v$ paths that the 2 subproblem solutions refer to all need to be extended by 1 weight-$k$ edge. $\endgroup$ – j_random_hacker Jan 18 at 12:36
  • $\begingroup$ Thanks for revising the answer. One more note as I'm not sure if I understood your approach for converting arbitrary trees to binary ones. I've drawn an example. Here children from the original tree are always encoded as a left child in binary tree and edges to left childs have weight 1. Remaining edges (those to right children) have 0 weight. I thought about using Wikipedia procedure for encoding m-trees as binary trees, but it changes some leaves into internal nodes. $\endgroup$ – dzieciou Jan 18 at 18:25
  • $\begingroup$ @j_random_hacker, ooh, good point! Fixed. $\endgroup$ – D.W. Jan 18 at 20:03
  • 1
    $\begingroup$ @dzieciou, yup, that looks like it should work! (I was imagining something slightly different but yours should work just as well.) $\endgroup$ – D.W. Jan 18 at 20: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.