This problem comes up in the context of game skilltrees, for example in Path of Exile. In this case, one wants to have a subgraph of the entire graph that connects all desired nodes to the origin, but contains as few nodes as possible. Is there an efficient algorithm for this, or a good heuristic? Or is it, as I suspect, NP-hard?
Simply using Dijkstra to determine the distances and then Kruskal to find a minimum spanning tree does not work. This is because the cost of connecting a subsequent node can depend on what nodes are already connected (and by which paths).