Can any tree on $n$ nodes be decomposed into a set of $O(\log n)$ caterpillars? 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.
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.
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. Just take the maximal heavy-edge paths as the spines of the caterpillars.
