GATE CS 2005 Q82b — Graph Traversals (BFS, DFS)

This problem asks us to find a path between $s$ and $t$ that minimizes the maximum edge weight on the path. This is known as the bottleneck shortest path or minimax path problem.

Proof using the Cut Property of MSTs

Let $T$ be the Minimum Spanning Tree (MST) of the graph $G$. Since the edge weights are distinct, $T$ is unique. Let $P_T$ be the unique path between $s$ and $t$ in $T$.

1. Let $e = (u, v)$ be the edge on $P_T$ with the maximum weight. Thus, the congestion of $P_T$ is $w(e)$.
2. Removing the edge $e$ from $T$ partitions the vertices of $T$ (and hence $G$) into two disjoint sets, $X$ and $Y$, such that $s \in X$ and $t \in Y$.
3. By the cut property of MSTs, the edge $e$ must be the minimum-weight edge in $G$ that crosses the cut $[X, Y]$. That is, for any other edge $e'$ crossing $[X, Y]$, we have: $$w(e') > w(e)$$
4. Any path $P$ from $s$ to $t$ in $G$ must cross the cut $[X, Y]$ at least once. Therefore, $P$ must contain at least one edge $e'$ that has one endpoint in $X$ and the other in $Y$.
5. The maximum edge weight (congestion) on $P$ is at least $w(e')$. Since $w(e') \ge w(e)$, the congestion of $P$ is at least $w(e)$.

Thus, no path from $s$ to $t$ can have a smaller congestion than the path $P_T$ in the MST.

Why other options are incorrect:

• Option B (Weighted shortest path): Minimizes the sum of edge weights, which does not necessarily minimize the maximum single edge weight. For example, a path with edges of weights $\{4, 4\}$ (sum $= 8$, max $= 4$) might be chosen over a single-edge path of weight $\{5\}$ (sum $= 5$, max $= 5$) by a bottleneck algorithm, but a shortest path algorithm would choose the path of weight $5$.
• Options C and D: Euler walks and Hamiltonian paths do not always exist in a graph, and even when they do, they do not minimize the bottleneck edge weight.