How to induce a minimal subgraph

  • Context: Graduate 
  • Thread starter Thread starter cynthiaj
  • Start date Start date
Click For Summary
SUMMARY

The discussion centers on the challenge of inducing a minimal subgraph from an undirected graph G, specifically focusing on a subset S of nodes. The goal is to connect as many nodes in S as possible while including the fewest additional nodes from outside S. Participants inquire about the existence of such a subgraph and whether an algorithm can be employed to construct it. The conversation highlights the need for clarity on whether the inquiry pertains to theoretical existence or practical algorithmic solutions.

PREREQUISITES
  • Understanding of undirected graphs and vertex-induced subgraphs
  • Familiarity with graph connectivity concepts
  • Basic knowledge of graph algorithms
  • Experience with theoretical graph theory principles
NEXT STEPS
  • Research algorithms for constructing minimal spanning trees in graphs
  • Explore the concept of connected components in graph theory
  • Learn about the Dijkstra's algorithm for finding shortest paths
  • Investigate the theory behind subgraph existence proofs
USEFUL FOR

This discussion is beneficial for graph theorists, computer scientists, and software engineers involved in network design, optimization problems, and algorithm development related to graph structures.

cynthiaj
Messages
2
Reaction score
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
 
Mathematics news on Phys.org
cynthiaj said:
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?
 
Stephen Tashi said:
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
 

Similar threads

Undergrad Find Smallest Subtree of G w/ Nodes from S
  • · Replies 5 ·
Replies
5
Views
2K
High School Can you read my English on 4 colour theorem?
  • · Replies 8 ·
Replies
8
Views
2K
Strong Induction, Tangled Graph
  • · Replies 3 ·
Replies
3
Views
3K
Graduate Cross section from subgraph in electron-proton DIS
  • · Replies 3 ·
Replies
3
Views
2K
Graduate Is Your Graph Homeomorphic to a Sphere?
  • · Replies 3 ·
Replies
3
Views
2K
Python Help solving a geometrical matching issue with Graph Neural Networks
  • · Replies 1 ·
Replies
1
Views
3K
Graduate Does This Graph Structure Form a Matroid?
  • · Replies 1 ·
Replies
1
Views
2K
Is Every Induced Subgraph with a Cut-Vertex a Block?
  • · Replies 1 ·
Replies
1
Views
2K
Proving Cut Vertices in Simple Graphs
  • · Replies 2 ·
Replies
2
Views
2K
Undergrad Optimization problem with multiple outputs: impossible?
  • · Replies 6 ·
Replies
6
Views
3K