<p>It seems this is false in general. Take the tree with a central node $x$, connected to a bunch of nodes $y_1,\dots,y_n$. Each node $y_i$ is additionally connected to a node $z_i$.</p>

<p>The total number of nodes is $N=2n+1$.</p>

<p>Any caterpillar in this tree can contain at most two $z$ nodes, and therefore, $n/2$ caterpillars are needed to cover it. So it is impossible to cover it with $O(log N)$ caterpillars.</p>

CC BY-SA 3.0
2013-03-07T17:14:42.603Z
2013-03-07T17:14:42.603Z
Denis
<p>I would like to add to dkuper's answer that it is possible to split every tree into a <em>hierarchy</em> of caterpillars, whose depth is at most $O(\log n)$. This can be done with Tarjan's <a href="http://wcipeg.com/wiki/Heavy-light_decomposition">heavy-light edge decompostion</a>. Just take the maximal heavy-edge paths as the spines of the caterpillars.</p>

CC BY-SA 3.0
2013-03-08T09:47:31.913Z
2013-03-08T09:47:31.913Z
A.Schulz
<p>Can any tree on $n$ nodes be decomposed into a set of $O(\log n)$ <a href="http://en.wikipedia.org/wiki/Caterpillar_tree">caterpillars</a>? If not, what is the maximum number of caterpillars required? Are there efficient algorithms for finding the decomposition?</p>

<p>Any papers on this topic will be highly appreciated.</p>

<ds.algorithms><graph-theory><graph-algorithms><tree>
Caterpillar decomposition of trees
Arindam Pal
# Caterpillar decomposition of trees

(Asked by: username_0 on 2013-03-07)

Can any tree on $n$ nodes be decomposed into a set of $O(\log n)$ [caterpillars](http://en.wikipedia.org/wiki/Caterpillar_tree)? If not, what is the maximum number of caterpillars required? Are there efficient algorithms for finding the decomposition?

Any papers on this topic will be highly appreciated.

**Tags:** ds.algorithms, graph-theory, graph-algorithms, tree


---

## 2 answers

### Answer by username_1 on 2013-03-07. Score: 12

It seems this is false in general. Take the tree with a central node $x$, connected to a bunch of nodes $y\_1,\dots,y\_n$. Each node $y\_i$ is additionally connected to a node $z\_i$.

The total number of nodes is $N=2n+1$.

Any caterpillar in this tree can contain at most two $z$ nodes, and therefore, $n/2$ caterpillars are needed to cover it. So it is impossible to cover it with $O(log N)$ caterpillars.


---

### Answer by username_2 on 2013-03-08. Score: 8

I would like to add to dkuper's answer that it is possible to split every tree into a *hierarchy* of caterpillars, whose depth is at most $O(\log n)$. This can be done with Tarjan's [heavy-light edge decompostion](http://wcipeg.com/wiki/Heavy-light_decomposition). Just take the maximal heavy-edge paths as the spines of the caterpillars.


---

