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

Definition1

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

Lemma2

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

Theorem3

$A ≼ A^{'}$ , $B ≼ B^{'}$ then $A \cup B ≼ A^{'} \cup B^{'}$

Proof

Let $C = A \cup B$ and $C^{'} = A^{'} \cup 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^{'} = \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^{'} ≼ 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 ≼ A^{'} - c$ .

Assume $c \in A$ , then $c \in A^{'}$ , so by previous lemma this is true.
If $c \neq \in A$ and $c \neq \in A^{'}$ , then $A - c = A ≼ A^{'} = A^{'} - c$ .
If $c \neq \in A$ but $c \in A^{'}$ , then this implies $A$ is empty, and $\emptyset ≼ A^{'} - c$ .

Similarly, $B - c ≼ B^{'} - c$ .

Second, we need to show that $(A^{'} - c) \cup (B^{'} - c) ≼ (A - c) \cup (B - c)$ . This is obvious because $C^{'} ≼ C$ implies $C^{'} - c ≼ 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}, \dots, e_{m}$ . Let $w (e_{i}) = i$ .

Problem4Bottleneck Shortest Path

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

Any $s t$ -path that maximizes the minimum edge weight over all $s t$ -paths is a $s t$ -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.

Problem5Lexicographic Bottleneck Shortest Path

Find a $s t$ -path $P$ such that $P^{'} ≼ P$ for all $s t$ -path $P^{'}$ .

The unique $s t$ -path that is maximum in lexicographic bottleneck order among all $s t$ -paths is called the $s t$ -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 $s t$ -path in $T$ is a $s t$ -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 $s t$ -path in $T$ is the $s t$ -LBSP in $G$ .

Before proving the theorem, we consider a useful lemma.

Lemma8

$P$ is a $s t$ -BSP with bottleneck edge $x y$ . If removing edge $x y$ result a $s x$ -LBSP and $y t$ -LBSP, then $P$ is a $s t$ -LBSP.

Proof

$P$ is a bottleneck $s t$ -path implies the $s t$ -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 $y t$ -LBSP would imply $x y$ is not in $s t$ -LBSP, a contradiction.

Thus, we must have the $s t$ -LBSP is a concatenation of $3$ paths, a $s x$ -path $P_{s x}$ , edge $x y$ and a $y t$ -path $P_{t y}$ . 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 $s t$ -BSP with bottleneck edge $x y$ . By the inductive hypothesis, removing $x y$ result a $s x$ -LBSP and $y t$ -LBSP in $G$ . The previous lemma demonstrates that $s t$ -BSP in $T$ is a $s t$ -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.