Is there an algorithm to cut a non-binary tree into a minimal number of sub-trees with a given maximum depth?
Example: Given this non-binary tree with node A as its root. Cut the tree into a minimal number of sub-trees with a maximum depth of 2.
In the example the cut would need to be performed between nodes A-B or B-G to achieve the desired result.
Each edge removal partitions the tree into two subtrees, so minimizing the number of subtrees is equivalent to minimizing the number of removed edges. One approach is to use dynamic programming. Let $f(T)$ be the desired minimum number of removed edges for tree $T$. The boundary case is $f(T)=0$ if $T$ has depth at most two. Otherwise, $$f(T) = 1 + \min_{(i,j)\in E(T)} \{f(T_1) + f(T_2)\},$$ where $T_1$ and $T_2$ are the two subtrees obtained by removing edge $(i,j)$.