Skip to main content
AI Assist is now on Stack Overflow. Start a chat to get instant answers from across the network. Sign up to save and share your chats.

Return to Question

Commonmark migration
Source Link
Community Bot
Community Bot
  • 1
  • 1

I need help with this problem that I'm currently working on, which involves finding a node v in an undirected graph that, when removed, will destroy all paths between two other nodes s and t.

Suppose that an n-node undirected graph G = (V, E) contains two nodes s and t such that the distance between s and t is strictly greater than n/2. Show that there must exist some node v, not equal to either s or t, such that deleting v from G destroys all s-t paths. (In other words, the graph obtained from G by deleting v contains no path from s to t.)

 

Give an algorithm with running time O(m + n) to find such a node v.
(For solution, you can use either plain English or pseudo code.)

My understanding of this is that the solution would involve creating a breadth-first search that finds the node v and removes it, but I'm not certain of how to prove that removing the node exists in the first place such that removing it would destroy all s-t paths.

I need help with this problem that I'm currently working on, which involves finding a node v in an undirected graph that, when removed, will destroy all paths between two other nodes s and t.

Suppose that an n-node undirected graph G = (V, E) contains two nodes s and t such that the distance between s and t is strictly greater than n/2. Show that there must exist some node v, not equal to either s or t, such that deleting v from G destroys all s-t paths. (In other words, the graph obtained from G by deleting v contains no path from s to t.)

 

Give an algorithm with running time O(m + n) to find such a node v.
(For solution, you can use either plain English or pseudo code.)

My understanding of this is that the solution would involve creating a breadth-first search that finds the node v and removes it, but I'm not certain of how to prove that removing the node exists in the first place such that removing it would destroy all s-t paths.

I need help with this problem that I'm currently working on, which involves finding a node v in an undirected graph that, when removed, will destroy all paths between two other nodes s and t.

Suppose that an n-node undirected graph G = (V, E) contains two nodes s and t such that the distance between s and t is strictly greater than n/2. Show that there must exist some node v, not equal to either s or t, such that deleting v from G destroys all s-t paths. (In other words, the graph obtained from G by deleting v contains no path from s to t.)

Give an algorithm with running time O(m + n) to find such a node v.
(For solution, you can use either plain English or pseudo code.)

My understanding of this is that the solution would involve creating a breadth-first search that finds the node v and removes it, but I'm not certain of how to prove that removing the node exists in the first place such that removing it would destroy all s-t paths.

Source Link
user2309750
user2309750
  • 1.6k
  • 4
  • 14
  • 12

Removing a node in an undirected graph that destroys a path between two other nodes

I need help with this problem that I'm currently working on, which involves finding a node v in an undirected graph that, when removed, will destroy all paths between two other nodes s and t.

Suppose that an n-node undirected graph G = (V, E) contains two nodes s and t such that the distance between s and t is strictly greater than n/2. Show that there must exist some node v, not equal to either s or t, such that deleting v from G destroys all s-t paths. (In other words, the graph obtained from G by deleting v contains no path from s to t.)

Give an algorithm with running time O(m + n) to find such a node v.
(For solution, you can use either plain English or pseudo code.)

My understanding of this is that the solution would involve creating a breadth-first search that finds the node v and removes it, but I'm not certain of how to prove that removing the node exists in the first place such that removing it would destroy all s-t paths.