19
$\begingroup$

In the following, we consider binary trees where only the leaves have weights. Let $T$ be a binary tree and $W(T)$ be the sum of the weights of its leaves. Let $T.l$ and $T.r$ be the left child and right child respectively.

We define the imbalance $I(T)$ of a binary tree $T$ as follows:

$$I(T) = \begin{cases} 0 & size(T) = 1\\ |W(T.l) - W(T.r)| + I(T.l) + I(T.r) & size(T)>0 \end{cases}$$

Examples

  a.)  *        b.)  *
      / \          /   \
     *   5        *     *
    / \          / \   / \
   *   3        1   5 3   3
  / \
 1   3

Tree a. has imbalance 5 (2 + 1 + 2) and tree b. has imbalance 4 (4 + 0 + 0).


Consider the following problem:

Input: a list of $n$ positive integers $W = (a_1, \ldots, a_n)$, and an integer $k$.

Query: is there a binary tree $T$ with leaf weights $W$ such that $I(T) \leq k$?

Is this problem $\mathsf{NP}$-hard?


The case $k = 0$ is easy. There is a simple algorithm which goes as follows ($Q$ is a priority queue):

  1. for $w \in W$: $Q.push(w)$
  2. while $Q.size > 1$:
    2.1. pop the two smallest elements $w_1$ and $w_2$ form $Q$.
    2.2. if $w_1 = w_2$ then $Q.push(2*w_1)$
    2.3. else return "No"
  3. return "Yes"
$\endgroup$
5
  • 3
    $\begingroup$ Just to rule out simple reduction - can you think of a case where the set of weights has equal-weight partition and the optimal tree doesn't partition the leafs accordingly? $\endgroup$
    – R B
    Commented Jan 10, 2015 at 13:44
  • 3
    $\begingroup$ @RB If I understand your comment correctly, $\{1,2,3,4\}$ would be an example. Equal weight partition gives [[1 4][2 3]] (imbalance 4) where as the optimal tree is [4 [3 [2 1]]] (imbalance 3). $\endgroup$
    – rex123
    Commented Jan 22, 2015 at 20:36
  • $\begingroup$ What have you tried so far? Have there been attempts on reductions? $\endgroup$ Commented Oct 26, 2018 at 13:34
  • 1
    $\begingroup$ I believe the dynamic programming algorithm by Knuth for optimal binary search trees is close to what you want. $\endgroup$
    – vonbrand
    Commented Aug 20, 2019 at 15:42
  • $\begingroup$ @vonbrand Theres one huge difference of the elements being ordered in the problem statement for knuth's algo. Here the elements can be permuted to any way we want. $\endgroup$
    – EnEm
    Commented 2 days ago

1 Answer 1

0
$\begingroup$

Not a complete answer, but an intuition to see that the problem is highly likely to be NP-complete.

This problem has optimal substructure property, i.e., in an optimal tree $T$, trees $T.l$ and $T.r$ will also be optimal for their corresponding subset of leaves.

Then, lets say you have two polynomial time methods $w, s: \mathcal{P}(W) \setminus \{\emptyset, W\} \rightarrow \mathbb{N}_0$ which denote the $W(T)$ and $I(T)$ of the optimal tree for any proper subset $H\subset W$.

Then our task remains to find the subset $H_0 \subset W$ where $s(W) = |w(H_0) - w(W\setminus H_0) | + s(H_0) + s(W\setminus H_0)$ is $\le k$. This is very similar to the partition problem to be solvable in polynomial time. Idea is that there can be an adversary which fine tunes on the list $W$ and $k$ such that the above problem becomes ewuivalent to the partition problem.

New contributor
EnEm is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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