Lexicographic Bottleneck Shortest Path in Undirected Graphs
1 Lexicographic Bottleneck Ordering
Let be a totally ordered set. Let be the sorted sequence of all the elements in , where . We can induce an total ordering on the subset of .
for if in lexicographic ordering. is called the lexicographic bottleneck ordering.
For nonempty sets and , if , then . Also if then .
Let and .
Since is a total order, we can prove it by showing if then .
We prove it by structural induction on . The base case when is trivial, since it must mean .
Consider . in order for . But we know . This shows . Given that , if and only if .
First, we show that .
- Assume , then , so by previous lemma this is true.
- If and , then .
- If but , then this implies is empty, and .
Second, we need to show that . This is obvious because implies .
By the inductive hypothesis, , thus completes the proof.
The theorem intuitively tells us how to partition a set into smaller sets.
2 Lexicographic Bottleneck Path
Given a undirected graph , and an ordering of the edges . Let .
Find a -path that maximizes the minimum edge weight on the path.
Any -path that maximizes the minimum edge weight over all -paths is a -bottleneck shortest path(BSP). We are interested in a more general version of this problem. Find a path from to that is maximum with respect to the lexicographic bottleneck ordering of the path.
Find a -path such that for all -path .
The unique -path that is maximum in lexicographic bottleneck order among all -paths is called the -lexicographic bottleneck shortest path(LBSP).
In order to find a BSP, we can first compute the maximum spanning tree of , as show in Lemma 4.1 of .
If is a maximum spanning tree of (under the weight ), then the unique -path in is a -BSP in .
It’s interesting this theorem actually extends to LBSP.
If is a maximum spanning tree of (under the weight ), then the unique -path in is the -LBSP in .
Before proving the theorem, we consider a useful lemma.
is a -BSP with bottleneck edge . If removing edge result a -LBSP and -LBSP, then is a -LBSP.
is a bottleneck -path implies the -LBSP has to reach either or before .
If it reaches before , then the subpath from to then from to using the -LBSP would imply is not in -LBSP, a contradiction.
Thus, we must have the -LBSP is a concatenation of paths, a -path , edge and a -path . Using Theorem 3, we notice is a LBSP.
We prove by induction on the distance between the two vertices on the maximum spanning tree .
Base Case: If the length of a on is , then the edge is a BSP, and also a LBSP.
Inductive Step: Consider two vertices and . The tree induces a -BSP with bottleneck edge . By the inductive hypothesis, removing result a -LBSP and -LBSP in . The previous lemma demonstrates that -BSP in is a -LBSP in .
 A. Shapira, R. Yuster, U. Zwick, All-pairs bottleneck paths in vertex weighted graphs, Algorithmica. 59 (2011) 621–633 10.1007/s00453-009-9328-x.