minimum connected subgraph containing a fixed set

Let $G=(V,E)$ be a connected graph, and let $S\subset V$. How to find a minimum subset $H\supset S$,and $G(H)$ is a connected graph.

It seems different from Steiner tree problem. Since in Steiner tree problem, the weight is added in edges and the goal is to find a tree. While in our problem, the goal is to find a induced subgraph.

• This seems like a generalised path-finding algorithm, which would be the special case $|S|=2$. Sep 17 '17 at 11:32

Your problem is as hard as the Steiner tree problem for unweighted graphs. $G(H)$ might contain cycles, but a solution $H$ for your problem is a solution for the unweighted Steiner tree problem, since $G(H)$ is connected and therefore contains a spanning tree.