I am currently working through exercise 9.b) on Page 270 of Jeff Erickson's Algorithms book
Consider a path between two vertices s and t in a undirected weighted graph G. The width of this path is the minimum weight of any edge in the path. The bottleneck distance between s and t is the width of the widest path from s to t. (If there are no paths from s to t, the bottleneck distance is −∞; on the other hand, the bottleneck distance from s to itself is ∞.)
Describe an algorithm to solve the following problem in O(V + E) time: Given a undirected weighted graph G, two vertices s and t, and a weight W, is the bottleneck distance between s and t at most W?
I figured I can solve the problem in O(ElogE) time by modifying Kruskal's Algorithm to first find a maximum spanning tree and then use BFS to find the smallest weight on the path between s and t, however I don't really understand how this problem can be solved in O(E + V) time. I tried to modify the BFS algorithm in some way without any luck.
I was able to find a similar problem where it is asked to find if the bottleneck distance is at least W. This can easily be solved by deleting the edges with a weight less than W and using BFS to check if t is reachable from s. I don’t think this solution is directly adaptable, though. Any tips?
The problem can be rephrased as "is it impossible to connect s and t using edges with weight greater than W"
You already know how to run Kruskal's algorithm, so this is easy for you. No need to sort the edges. Just add all the edges with weight > W and see if s and t are connected. Or DFS/BFS over the subgraph with those edges.