0
$\begingroup$

Given an undirected and unweighted graph $G = (V, E)$ and two of its vertices $s$ and $t$. My task is to find an algorithm that checks if there exists an edge belonging to $E$ such that its removal will result in the shortest path from $s$ to $t$ being extended (and if so returns this edge). We may remove only one edge.

In practice, a graph is given as a list of lists. The $i$-th list contains the numbers of vertices adjacent to the $i$-th vertex (numbered from 0).

Example:
$G = [ [1,2], [0,2], [0,1] ]$
$s = 0$
$t = 2$

The answer is an edge terminated by vertices 0 and 2 - the shortest path has been extended from 1 to 2.

How can this problem be solved in optimal time?

All I know is that the best way to find the shortest path in a basic graph like this is to just use BFS, and I guess I have to use it somehow here as well, but otherwise I have no idea how to approach this...

$\endgroup$
2
  • 2
    $\begingroup$ What did you try? Where did you get stuck? Where did you encounter this task? What's the best algorithm you've got so far? We're happy to help you understand the concepts but just solving exercise-like tasks for you is unlikely to achieve that. We're not looking for posts that are just the statement of an exercise-like task. You might find this page helpful in improving your question. $\endgroup$
    – D.W.
    May 4 at 0:33
  • $\begingroup$ Please edit your question to include what you tried and what you found perplexing and/or what you found to be an obstacle in your partial solution. $\endgroup$ May 4 at 1:04

1 Answer 1

2
$\begingroup$

the Idea

Find all edges that are on one of the shortest paths from $s$ to $t$. Find the bridges in the graph that consists of those edges.

the Approach

  1. Use breadth-first-search to compute $d_s(u)$, the distance from $s$ to $u$ for each vertex $u$. If $t$ is found not reachable from $s$, return nothing.
  2. Ditto for $d_t(v)$.
  3. Collect all edges $(u,v)$ such that $d_s(u) + d_t(v) = d_s(t)-1$ as graph $S$.
  4. Try running a linear algorithm that finds all bridges in $S$ such as this one. As soon as one bridge has been found, return it.
  5. Return nothing.

An algorithm that implements the approach above runs in linear time.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.