Finding the smallest subtree

Question

Given a graph of n nodes that are all interconnected on a coordinate plane, what's the best way to find a subtree of minimal distance that contains m nodes?

The only solution I've found to this problem is to generate all combinations of the nodes to connect and attempt to connect these nodes via either Kruskal's or Prim's algorithm while disregarding the rest, then compare all trees created and find the smallest one, but this isn't exactly efficient when it comes to larger trees.

Is there a faster, more efficient algorithm/method?

Answer 1

You are asking about the K-minimum spanning tree (k-MST) problem, which is known to be NP-complete. So you're not going to do much better than your current algorithm.

However, in the comments, you say that your graph is generated from a coordinate plane, so I can only assume that you have some geometric information about the nodes in the graph. The WWW compendium entry mentions that you can use a polynomial-time approximation scheme for Euclidean k-MST. This paper describes one:

Arora, Sanjeev. (1996), Polynomial time approximation scheme for Euclidean TSP and other geometric problems, In Proceedings of the 37th Ann. IEEE Symp. on Foundations of Computer Science, pages 2-11.

They mention k-MST directly in there, so I think you could try that algorithm if you really want more speed.