# 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\subset X$$. We can induce an total ordering on the subset of $$X$$.

Definition1

$$S\preccurlyeq T$$ for $$S,T\subset X$$ if $$l(S)\leq l(T)$$ in lexicographic ordering. $$\preccurlyeq$$ is called the lexicographic bottleneck ordering.

Lemma2

For nonempty sets $$A$$ and $$B$$, if $$A\preccurlyeq B$$ , then $$A - min A \preccurlyeq B - min B$$. Also if $$A\preccurlyeq B$$ then $$A \preccurlyeq A\cup B \preccurlyeq B$$.

Theorem3

$$A\preccurlyeq A'$$, $$B\preccurlyeq B'$$ then $$A\cup B \preccurlyeq A'\cup B'$$

Proof

Let $$C=A\cup B$$ and $$C' = A'\cup B'$$.

Since $$\preccurlyeq$$ is a total order, we can prove it by showing if $$C'\preccurlyeq C$$ then $$C' = C$$.

We prove it by structural induction on $$C'$$. The base case when $$C' = \emptyset$$ is trivial, since it must mean $$A=B=A'=B'=\emptyset$$.

Consider $$c' = \min C', c = \min C$$. $$c'\leq c$$ in order for $$C'\preccurlyeq C$$. But we know $$c\leq c'$$. This shows $$c=c'$$. Given that $$c=c'$$, $$A'\cup B' = A\cup B$$ if and only if $$(A'-c)\cup (B'-c) = (A-c) \cup (B-c)$$.

First, we show that $$A-c \preccurlyeq A'-c$$.

1. Assume $$c\in A$$, then $$c\in A'$$, so by previous lemma this is true.
2. If $$c\not\in A$$ and $$c\not \in A'$$, then $$A-c=A\preccurlyeq A'=A'-c$$.
3. If $$c\not \in A$$ but $$c\in A'$$, then this implies $$A$$ is empty, and $$\emptyset \preccurlyeq A'-c$$.

Similarly, $$B-c\preccurlyeq B'-c$$.

Second, we need to show that $$(A'-c)\cup (B'-c) \preccurlyeq (A-c) \cup (B-c)$$. This is obvious because $$C'\preccurlyeq C$$ implies $$C'-c \preccurlyeq C-c$$.

By the inductive hypothesis, $$(A'-c)\cup (B'-c) = (A-c) \cup (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,\ldots,e_m$$. Let $$w(e_i)=i$$.

Problem4Bottleneck Shortest Path

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 $$\preccurlyeq$$ of the path.

Problem5Lexicographic Bottleneck Shortest Path

Find a $$st$$-path $$P$$ such that $$P'\preccurlyeq 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].

Theorem6

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.

Theorem7

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.

Lemma8

$$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.

Proof

$$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.

ProofTheorem 7

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

[1] 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.

Posted by Chao Xu on 2014-05-10.
Tags: algorithm.