# How to find a minimum spanning forest with a constrained number of nodes in each spanning tree?

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.

• Your condition (4) is a bit ambiguous. I take it that you want every target vertex to be connected by some path to exactly one of the m source vertices (possibly a different source vertex in each case)? – j_random_hacker May 24 '18 at 12:18
• Yes, condition (4) is that every target vertex is connected by one and only one path originated from one source vertex. Thanks for the revision. – John Bai Jun 17 '18 at 16:32
• If a graph is undirected and acyclic then it is necessarily a forest (collection of trees). Is that what you meant? (I think the problem still seems interesting in this case, just checking.) – j_random_hacker Jun 18 '18 at 5:22