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.

  • $\begingroup$ 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)? $\endgroup$ May 24 '18 at 12:18
  • $\begingroup$ 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. $\endgroup$
    – John Bai
    Jun 17 '18 at 16:32
  • $\begingroup$ 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.) $\endgroup$ Jun 18 '18 at 5:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.