# Lexicographic Bottleneck Shortest Path in Undirected Graphs

# 1 Lexicographic Bottleneck Ordering

Let $X$ be a totally ordered set. Let $l(S)$ be the sorted sequence of all the elements in $S$, where $S⊂X$. We can induce an total ordering on the subset of $X$.

$S≼T$ for $S,T⊂X$ if $l(S)≤l(T)$ in lexicographic ordering. $≼$ is called the lexicographic bottleneck ordering.

For nonempty sets $A$ and $B$, if $A≼B$ , then $A−minA≼B−minB$. Also if $A≼B$ then $A≼A∪B≼B$.

$A≼A_{′}$, $B≼B_{′}$ then $A∪B≼A_{′}∪B_{′}$

Let $C=A∪B$ and $C_{′}=A_{′}∪B_{′}$.

Since $≼$ is a total order, we can prove it by showing if $C_{′}≼C$ then $C_{′}=C$.

We prove it by structural induction on $C_{′}$. The base case when $C_{′}=∅$ is trivial, since it must mean $A=B=A_{′}=B_{′}=∅$.

Consider $c_{′}=minC_{′},c=minC$. $c_{′}≤c$ in order for $C_{′}≼C$. But we know $c≤c_{′}$. This shows $c=c_{′}$. Given that $c=c_{′}$, $A_{′}∪B_{′}=A∪B$ if and only if $(A_{′}−c)∪(B_{′}−c)=(A−c)∪(B−c)$.

First, we show that $A−c≼A_{′}−c$.

- Assume $c∈A$, then $c∈A_{′}$, so by previous lemma this is true.
- If $c∈A$ and $c∈A_{′}$, then $A−c=A≼A_{′}=A_{′}−c$.
- If $c∈A$ but $c∈A_{′}$, then this implies $A$ is empty, and $∅≼A_{′}−c$.

Similarly, $B−c≼B_{′}−c$.

Second, we need to show that $(A_{′}−c)∪(B_{′}−c)≼(A−c)∪(B−c)$. This is obvious because $C_{′}≼C$ implies $C_{′}−c≼C−c$.

By the inductive hypothesis, $(A_{′}−c)∪(B_{′}−c)=(A−c)∪(B−c)$, 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 $G=(V,E)$, and an ordering of the edges $e_{1},…,e_{m}$. Let $w(e_{i})=i$.

Find a $st$-path that maximizes the minimum edge weight on the path.

Any $st$-path that maximizes the minimum edge weight over all $st$-paths is a $st$-bottleneck shortest path(BSP). We are interested in a more general version of this problem. Find a path from $s$ to $t$ that is maximum with respect to the lexicographic bottleneck ordering $≼$ of the path.

Find a $st$-path $P$ such that $P_{′}≼P$ for all $st$-path $P_{′}$.

The unique $st$-path that is maximum in lexicographic bottleneck order among all $st$-paths is called the $st$-lexicographic bottleneck shortest path(LBSP).

In order to find a BSP, we can first compute the maximum spanning tree $T$ of $G$, as show in Lemma 4.1 of [1].

If $T$ is a maximum spanning tree of $G$(under the weight $w$), then the unique $st$-path in $T$ is a $st$-BSP in $G$.

It’s interesting this theorem actually extends to LBSP.

If $T$ is a maximum spanning tree of $G$(under the weight $w$), then the unique $st$-path in $T$ is the $st$-LBSP in $G$.

Before proving the theorem, we consider a useful lemma.

$P$ is a $st$-BSP with bottleneck edge $xy$. If removing edge $xy$ result a $sx$-LBSP and $yt$-LBSP, then $P$ is a $st$-LBSP.

$P$ is a bottleneck $st$-path implies the $st$-LBSP has to reach either $x$ or $y$ before $t$.

If it reaches $y$ before $x$, then the subpath from $s$ to $y$ then from $y$ to $t$ using the $yt$-LBSP would imply $xy$ is not in $st$-LBSP, a contradiction.

Thus, we must have the $st$-LBSP is a concatenation of $3$ paths, a $sx$-path $P_{sx}$, edge $xy$ and a $yt$-path $P_{ty}$. Using Theorem 3, we notice $P$ is a LBSP.

We prove by induction on the distance between the two vertices on the maximum spanning tree $T$.

**Base Case:** If the length of a $uv$ on $T$ is
$1$, then the edge $uv$ is a BSP, and also a LBSP.

**Inductive Step:** Consider two vertices $s$ and $t$. The
tree induces a $st$-BSP with bottleneck
edge $xy$. By the inductive hypothesis,
removing $xy$ result a $sx$-LBSP and $yt$-LBSP in $G$. The previous lemma demonstrates that $st$-BSP in $T$
is a $st$-LBSP in $G$.

# References

**All-pairs bottleneck paths in vertex weighted graphs**, Algorithmica. 59 (2011) 621–633 10.1007/s00453-009-9328-x.