<p>The input is set of (disjoint) intervals $I$. The output should be the following rooted binary tree. Each leaf node corresponds to an interval from $I$. Each interior node contains an interval which encloses intervals from both child nodes. The goal is to minimize the sum of lengths of intervals in interior nodes.</p>

<p>Example. Input $I=\{[1,5], [7,9], [20,25]\}$</p>

<p>leaf nodes: $l_1 = [1,5], l_2 = [7,9], l_3=[20,25]$</p>

<p>interior nodes $i_1 = (l_1, l_2, [1,9]), i_2= (i_1, l_3,[1,25])$</p>

<p>Is this problem NP-hard? </p>

CC BY-SA 3.0
2016-03-06T16:01:19.163Z
You should be able to use dynamic programming to solve this in polynomial time.
Peter Shor 
CC BY-SA 3.0
2016-03-06T18:59:17.937Z
More precisely, you're asking for an alphabetical Huffman tree.
S. Pek
CC BY-SA 3.0
2016-03-06T22:32:55.180Z
@S. Pek: this is not quite an alphabetical Huffman tree. If you join the intervals [1,3] and [4,5] (weights 2 and 1, respectively), you get [1,5] (weight 4). In an alphabetic Huffman tree, it would be weight 3. I have no idea whether this breaks any of the alphabetic Huffman tree algorithms. If the intervals were all touching, it would be an alphabetic Huffman tree.
Peter Shor 
<np-hardness><binary-trees>
Is "Binary Interval Tree" NP-hard?
Esantin
# Is "Binary Interval Tree" NP-hard?

(Asked by: username_0 on 2016-03-05)

The input is set of (disjoint) intervals $I$. The output should be the following rooted binary tree. Each leaf node corresponds to an interval from $I$. Each interior node contains an interval which encloses intervals from both child nodes. The goal is to minimize the sum of lengths of intervals in interior nodes.

Example. Input $I=\{[1,5], [7,9], [20,25]\}$

leaf nodes: $l\_1 = [1,5], l\_2 = [7,9], l\_3=[20,25]$

interior nodes $i\_1 = (l\_1, l\_2, [1,9]), i\_2= (i\_1, l\_3,[1,25])$

Is this problem NP-hard?

**Tags:** np-hardness, binary-trees
> **Comments:**
> **username_1**: You should be able to use dynamic programming to solve this in polynomial time.  
> **username_2**: More precisely, you're asking for an alphabetical Huffman tree.  
> **username_1**: @S. Pek: this is not quite an alphabetical Huffman tree. If you join the intervals [1,3] and [4,5] (weights 2 and 1, respectively), you get [1,5] (weight 4). In an alphabetic Huffman tree, it would be weight 3. I have no idea whether this breaks any of the alphabetic Huffman tree algorithms. If the intervals were all touching, it would be an alphabetic Huffman tree.  

---

## 0 answers

