Skip to main content
2 of 3
added 256 characters in body
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

I assume you want to find a minimum covering. This problem is indeed NP-hard. For example, if $h=1$, then each tree is a star, and the problem reduces to computing a minimum vertex cover, which is NP-hard.

For an arbitrary $h$, let $G^h$ be the graph obtained from $G$ by replacing each edge of $G$ by a path with $h$ edges. It is easy to see that $G^h$ can be covered with $n$ trees of depth at most $h$ if and only if $G$ has a vertex cover of size $n$.

Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187