Consider a weighted undirected acyclic graph consists of m source (root) vertices and n target vertices. The m-spanning tree problem of the graph is defined as that: (1) each of the m spanning trees starts at one different root vertex and connects a subset of the n target vertices; (2) one root vertex might not connect any target vertex; (3) each two of the m different spanning trees do not contain any common target vertices; (4) all the target vertices are connected by the m root vertices.
The problem is to find a minimum m-spanning tree with the sum of the edge weights of all the m spanning trees be minimized, where the number of target vertices connected by each of the m spanning tree is not larger than a constant number. Is the problem NP-hard? If not, how to optimally solve it? Thanks very much for your comments and suggestions.