# Minimum bottleneck path between two vertices in an undirected graph

I have an undirected graph, where the value of the path is the maximum weight among all weights edges included in it. And I want find the path of minimum value between two given vertices in time $$O(n + m)$$, where $$n$$ - number of vertices, $$m$$ - number of edges.

I will use the fact that you can check for the connectivity between two vertices $$s$$ and $$t$$ in a graph with $$m>0$$ edges in time $$O(m)$$.

Call $$G$$ be the input graph, and let $$s$$ and $$t$$ be endpoints of the paths you are interested in. I will denote by $$G_w$$ (resp. $$G^<_w$$) the graph induced by all the edges of weight at most (resp. less than) $$w$$ in $$G$$. You can solve the problem using the following recursive algorithm:

If $$G$$ has no edges, report that $$s$$ and $$t$$ are disconnected in $$G$$.

If $$G$$ has at least one edge, find the median $$w$$ among the edge weights of $$G$$, and proceed as follows:

• If $$s$$ and $$t$$ are connected in $$G_w$$ and disconnected in $$G^<_w$$, return $$w$$.

• If $$s$$ and $$t$$ are connected in both $$G_w$$ and $$G^<_w$$, apply the algorithm recursively on $$G^<_w$$ (notice that $$G^<_w$$ has at most $$\frac{m}{2}$$ edges).

• If $$s$$ and $$t$$ are disconnected in $$G_w$$, build the graph $$G'$$ obtained from $$G$$ by identifying all vertices that belong to the same connected component of $$G_w$$, and apply the algorithm recursively on $$G'$$ (notice that $$G'$$ has at most $$\frac{m}{2}$$ edges, since it can't contain any edge with weight less than or equal to $$w$$).

The time complexity of the above algorithm is described by the recurrence equation: $$T(m) = T(m/2) + O(m)$$, which has solution $$T(m)=O(m)$$.

This problem is the same as its maximization version once all edge weights are multiplied by $$-1$$.

• You can explain what the cases mean: "Otherwise", "If this is not the case"? How do these cases differ? – Kapa Apr 26 '20 at 11:20
• I explicitly stated the condition for each of the cases. Is this clear now? – Steven Apr 26 '20 at 12:50
• Everything is clear, but what is the difference between $G_w$ and $G_w^{<}$ – Kapa Apr 26 '20 at 14:13
• $G_w$ is the graph induced by all the edges of weight at most $w$ in $G$. $G^<_w$ is the graph induced by all the edges of weight smaller than $w$ in $G$. An edge of weight $w$ is in $G_w$ but not in $G^<_w$. – Steven Apr 26 '20 at 14:27
• Maybe I'm wrong, but we run the procedure twice at each stage, and the recurrence equality will be different. – Kapa Apr 29 '20 at 21:16