The Art Gallery Guardian

Lexicographic Bottleneck Shortest Path in Undirected Graphs


1 Lexicographic Bottleneck Ordering

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

Definition1

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

Lemma2

For nonempty sets AA and BB, if ABA\preccurlyeq B , then AminABminBA - min A \preccurlyeq B - min B. Also if ABA\preccurlyeq B then AABBA \preccurlyeq A\cup B \preccurlyeq B.

Theorem3

AAA\preccurlyeq A', BBB\preccurlyeq B' then ABABA\cup B \preccurlyeq A'\cup B'

Proof

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

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

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

Consider c=minC,c=minCc' = \min C', c = \min C. ccc'\leq c in order for CCC'\preccurlyeq C. But we know ccc\leq c'. This shows c=cc=c'. Given that c=cc=c', AB=ABA'\cup B' = A\cup B if and only if (Ac)(Bc)=(Ac)(Bc)(A'-c)\cup (B'-c) = (A-c) \cup (B-c).

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

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

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

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

By the inductive hypothesis, (Ac)(Bc)=(Ac)(Bc)(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)G=(V,E), and an ordering of the edges e1,,eme_1,\ldots,e_m. Let w(ei)=iw(e_i)=i.

Problem4Bottleneck Shortest Path

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

Any stst-path that maximizes the minimum edge weight over all stst-paths is a stst-bottleneck shortest path(BSP). We are interested in a more general version of this problem. Find a path from ss to tt that is maximum with respect to the lexicographic bottleneck ordering \preccurlyeq of the path.

Problem5Lexicographic Bottleneck Shortest Path

Find a stst-path PP such that PPP'\preccurlyeq P for all stst-path PP'.

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

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

Theorem6

If TT is a maximum spanning tree of GG(under the weight ww), then the unique stst-path in TT is a stst-BSP in GG.

It's interesting this theorem actually extends to LBSP.

Theorem7

If TT is a maximum spanning tree of GG(under the weight ww), then the unique stst-path in TT is the stst-LBSP in GG.

Before proving the theorem, we consider a useful lemma.

Lemma8

PP is a stst-BSP with bottleneck edge xyxy. If removing edge xyxy result a sxsx-LBSP and ytyt-LBSP, then PP is a stst-LBSP.

Proof

PP is a bottleneck stst-path implies the stst-LBSP has to reach either xx or yy before tt.

If it reaches yy before xx, then the subpath from ss to yy then from yy to tt using the ytyt-LBSP would imply xyxy is not in stst-LBSP, a contradiction.

Thus, we must have the stst-LBSP is a concatenation of 33 paths, a sxsx-path PsxP_{sx}, edge xyxy and a ytyt-path PtyP_{ty}. Using Theorem 3, we notice PP is a LBSP.

ProofTheorem 7

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

Base Case: If the length of a uvuv on TT is 11, then the edge uvuv is a BSP, and also a LBSP.

Inductive Step: Consider two vertices ss and tt. The tree induces a stst-BSP with bottleneck edge xyxy. By the inductive hypothesis, removing xyxy result a sxsx-LBSP and ytyt-LBSP in GG. The previous lemma demonstrates that stst-BSP in TT is a stst-LBSP in GG.

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 .
Tags: algorithm.