Try k = 3. This is somewhat harder than k = 2.
Once you have done k = 3, k > 3 is easy.
You are given a weighted directed acyclic graph G, and a start node s in G. You are also given a positive integer k.
The problem is to find k directed paths starting at s, such that every node of G lies on at least one of those paths, and such that the sum of the weights of all the edges in the paths is minimized.
Try to work the problem with k = 1. This special case is too simple to be of much use (because there can be at most one path), but at least it gets you started.
Next, try k = 2. In this case, there is a solution whose time complexity is
polynomial in n, the number of nodes in G. If you get this far and can go
no farther, you have accomplished something. See an
example.
Try k = 3. This is somewhat harder than k = 2.
Once you have done k = 3, k > 3 is easy.