# Prune and search Algorithm for Generating a Bottleneck Spanning Tree

I'm trying to wrap my head around a prune-and-search algorithm for returning a bottleneck spanning tree, currently I'm selecting the median weight of all the edges, then divide the original graph G into two graphs containing the edges which are less than or equal to the median or greater than.

After separating the graphs, I test the median weight against the original graph (G) to see if it is a bottleneck value. I'm stuck on what to do, if the median is not a bottleneck value, I was thinking maybe I could compact the graph of edges with weights less than the median - but the cut of a compacted graph would still have the weights so the median wouldn't change. I'm thinking I need to form an MST at some point as well?

So far I have something like:

def F(G):
m = find_avg_weight_of_edges(G)
G_le_m = get_g_w_edge_weight_less_than_or_eqal_to(G,m)
G_gt_m = get_g_w_edge_weight_greater_than(G,m)
if is_bottleneck_value(G,x):
T = F(G_le_m)
else:
# note quite sure what to do...
# I can't remove the less than or equal to edges
# since they are needed to make up the MST
# but if I don't remove them m won't change
# maybe some kind of reduce/scc function?
return T


Let $$b$$ is the bottleneck edge of $$MBST$$, and let $$b$$ has weight $$w(b)$$.

Suppose $$e_{m}$$ is the median weighted edge of $$G$$, and let $$e_{m}$$ has weight $$w(e_{m})$$. Suppose $$G$$ gets partitioned into two subgraphs $$G_{1}$$ and $$G_{2}$$ such that edges in $$G_{1}$$ have weight $$\leq w(e_{m})$$ and edges in $$G_{2}$$ have weight $$> w(e_{m})$$.

If $$w(b) \leq w(e_{m})$$, then there must exist an $$MBST$$ within $$G_{1}$$ itself. Since the algorithm is recursing on $$G_{1}$$, it will output an $$MBST$$ if it exists. If the algorithm does not output a valid spanning tree, it means $$b \notin G_{1}$$. In other words, $$b \in G_{2}$$.

In that case, the algorithm will update $$e_{m}$$ to be the median weight edge of $$G_{2}$$. The graph $$G$$ will again get partitioned into two subgraphs $$G_{1}$$ and $$G_{2}$$. And, the algorithm can repeat this process.

• So what if graph $G$ has 3 Vertices $A,B,C$ with edge $w(AB)=1,w(BC)=3, w(e_m)=2$ So the algorithm now recurses on graph $G_2$ which has vertices $B,C$ - wont that just return an MST of $BC$, isn't there some kind of union or other operation that would need to happen with $G_1$? – Elliott de Launay Apr 11 at 14:21
• First of all, $e_{m}$ is the median weighted edge. For example, if edge set is $\{ 1,1,1,1,100\}$ then the $w(e_{m}) = 1$ and not $52$. – Inuyasha Yagami Apr 11 at 14:24
• Second, we are not recursing on $G_{2}$. – Inuyasha Yagami Apr 11 at 14:24
• We are just finding the median of $G_{2}$. That median will partition the entire graph $G$ into new subgraphs $G_{1}'$ and $G_{2}'$. Here, $G_{1}'$ already contains older $G_{1}$. Therefore, no union operation is required. – Inuyasha Yagami Apr 11 at 14:25
• Ah! Very good - thank you! – Elliott de Launay Apr 11 at 14:26