Let $G=(V,E)$ be an undirected graph and let $U \subset V$. Is there an algorithm that could find a minimal set of nodes that need to be added to $U$ so that the subgraph generated by the added nodes and nodes in $U$ is connected?
I know that such a set of added nodes is not usually unique. If finding such a set is very slow or almost impossible in big graphs, is there a way to a find such a set that it is quite close to being minimal?
This is known as the Steiner tree problem. Note that minimizing vertices or edges is the same, since the number of vertices of a steiner tree is $e+1-c$ (where $c$ is the number of connected components in the graph induced by $|U|$, and not counting edges between vertices of $U $)
This is a NP-hard problem, but you can find some good approximation results (see the link)