algorithmgraph-theorygraph-algorithmminimum-spanning-tree

Linear-Time algorithm for finding a mininum-bottleneck path


I'm taking an online algorithms class from Stanford, and one of the questions is as follows:

Define the bottleneck of a path to be the maximum length of one of its edges. A minimum-bottleneck path between two vertices s and t is a path with bottleneck no larger than that of any other s-t path. Suppose now that the graph is undirected. Give a linear-time (O(m)) algorithm to compute a minimum-bottleneck path between two given vertices.

Solving this with a modified Dijkstra's algorithm runs in O(mlog(n)) that doesn't meet the requirement. Wikipedia claims that there

exists a linear time algorithm for finding a widest s-t path in an undirected graph, that does not use the maximum spanning tree. The main idea of the algorithm is to apply the linear-time path-finding algorithm to the median edge weight in the graph, and then either to delete all smaller edges or contract all larger edges according to whether a path does or does not exist, and recurse in the resulting smaller graph.

There are couple of problems. The algorithm is mostly hand-waving, and I'm not looking for the widest path, but the opposite.

This paper has more text than Wikipedia, but it too, doesn't go into the gory details, especially when it comes to contracting the edges.

I've chalked out the following pseudocode:

1: MBP(G, s, t)
2:  if |E| == 1
3:    return the only edge
4:  else
5:    x = median of all edge weights
6:    E' = E - (v, w) where weight(v, w) < x
7:    construct G'(V, E')
8:    exists = is there a path from s to t in G'

9:    if (exists == FALSE)
10:      compute all the connected components Cᵢ of G'
11:      reinsert the edges deleted into G'

12:      G* = G'
13:      for each Cᵢ
14:        G* = SHRINK(G*, Cᵢ)

15:  return MBP(G', s, t)

16: SHRINK(G, C)
17:  leader = leader vertex of C
18:  V* = {V(G) - C} ∪ {leader}

19:  E* = {}
20:  for each edge (v, w) ∈ E(G)
21:    if v, w ∈ V*
22:      E* = E* ∪ {(v, w, weight(v, w))}
23:    else if v ∈ C, w ∈ V*
24:      E* = E* ∪ {(leader, w, max(weight(v, w)))}

25:  return G*(V*, E*)

Few things I don't understand:

  1. Line 6: how does it matter whether I delete the edges with weights higher than the median or lower?
  2. Line 20: There are 3 types of edges, those that have both vertices outside a connected component, those that have both vertices in the connected component, and those that have one vertex in the connected component, and one out. The first type retains it's edge weight, the second type becomes a self loop and should be deleted (?). What should be the edge weight for the third type?

Solution

  • OP here. A detail solution is found on my blog, but the pseudocode is as follows:

    1: CRITICAL-EDGE(G, s, t)
    2:   if |E(G)| == 1
    3:     return the only edge
    4:   else
    5:     x = median of all edge weights
    6:     X = E - (v, w) s.t. weight(v, w) > x
    7:     G' = G(V, X)
    8:     exists = is there a path from s to t in G'
    
    9:     if (exists == FALSE)
    10:      C = {C₁, C₂, ..., Cₖ} s.t. Cᵢ is a connected component of G
    11:      G' = G(V, E - X)
    
    12:      for i = 1 to |C|
    13:        G' = SHRINK(G', C, i)
    14:    else if X == E // no edges were deleted
    15:      X = {(v, w)} s.t. weight(v, w) = x
    16:      G' = G(V, X)
    
    17:  return CRITICAL-EDGE(G', s, t)
    
    18: SHRINK(G, C, i)
    19:   leaderᵢ = leader vertex of C[i]
    20:   V* = {V(G) - C[i]} ∪ {leaderᵢ}
    
    21:   E* = {}
    22:   for each (v, w) ∈ E(G)
    23:     if v ∈ C[i], w ∈ C[j]
    24:       E* = E* ∪ {(leaderᵢ, leaderⱼ, min(weight(u, w)))} ∀ u ∈ C[i]
    25:     else if v, w ∉ C[i]
              E * = E* ∪ {(v, w, weight(v, w))}
    
    26:   return G*(V*, E*)