The Art Gallery Guardian

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