How to induce a minimal subgraph

  • Thread starter cynthiaj
  • Start date
  • #1
2
0
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
 

Answers and Replies

  • #2
Stephen Tashi
Science Advisor
7,407
1,376
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?
 
  • #3
2
0
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
 

Related Threads on How to induce a minimal subgraph

Replies
2
Views
477
  • Last Post
Replies
9
Views
2K
  • Last Post
Replies
2
Views
2K
Replies
2
Views
2K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
1
Views
630
  • Last Post
Replies
2
Views
1K
Top