How to induce a minimal subgraph

[cynthiaj]

I have a undirected graph G and a subset S of nodes from G. If I only do vertex-induced subgraph for S, this subgraph might not be connected. What I want to do is to include as few as possible extra nodes outside S, and make as most as possible nodes in S are connected pairwisely through a path. Is there any way to accomplish this?

Thank you very much

 

[Stephen Tashi]

Is there any way to accomplish this?

I'm not a graph theorist, but I think you should clarify what it means to accomplish your goal. Are you asking whether there is an algorithm to construct the required subgraph? - or are you asking whether there is a theoretical argrument that the required subgraph exists?

 

[cynthiaj]

I'm not a graph theorist, but I think you should clarify what it means to accomplish your goal. Are you asking whether there is an algorithm to construct the required subgraph? - or are you asking whether there is a theoretical argrument that the required subgraph exists?

I would like to know whether such subgraph exists or not. If it does exist, is there an algorithm to obtain this subgraph