5

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.

Improve this question

1 Answer 1

Reset to default
11

First the prove part:

Let's assume v node does not exist which means there is at least two path using totally different nodes from s to t, and the distance is greater than n / 2. This is impossible since you do not even have enough number of nodes for this two path. So this contradicts our assumption there for v node exist.

Second part algorithm:

Use bidirectional BFS. Since v node's exist if you start to search from s and t, they will definitely meet at v nodes. And in the worst case you go thru all the V and E, so it is O(V + E).

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

I think I understand, but how does having at least two paths make the distance between greater than n/2? I thought the distance between s and t was the number of edges in the shortest path.
Because that's what said in your question "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. "

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.