Is there a way to find maximum bottleneck path in a DAG in O(|E|) time?

Question

I am working on a project and have a problem relating to finding a maximum bottleneck path from s to t in a directed acyclic graph. The problem is as follows:

Define the bottleneck of a path from s to t in a graph to be the smallest capacity out of the capacities of the edges in the path. Is it possible to find a path from s to t with the maximum bottleneck capacity in O(|E|) time, where |E| is the number of edges in the graph? How would I make such an algorithm?

Answer 1

You can do a breadth-first search for t starting at node s. As your graph is acyclic, this search is guaranteed to end, either returning all paths from s to t or no paths, if there is none such path.

• While searching keep track of all paths and their bottlenecks.
• When you reach an intermediate node x which was already visited via some other path, check, which of the known paths from s -> x has the highest bottleneck and keep only that one.
• The same also applies for t, ie if you reach t, check if you already have found any other path to t and keep only the path with the maximum bottleneck.
• Once the search has ended, only the path with the maximum bottleneck will remain (if there is any)

As this approach visits each edge at most once, it's in O(|E|)