I want an algorithm for the following problem. I have not find anything useful so far.
Given a undirected graph with costs assigned to the nodes, a positive number $n$ and a subset $S$ of the nodes, find a minimal cost subgraph with $n$ nodes that is connected and contains $S$. (If no such graph exists the algorithm should detect this.)
Is there such an algorithm? I know algorithms for spanning trees (Kruskal, Prim) but dont see a way to easily modify those.
Useful special cases or variants that I could have use for even if the entire problem is solved:
- The set $S$ contains just one node.
- The cost is zero for every node (that is we look for one solution ignoring the cost).
- The cost is assigned to the edges instead of to the nodes.