4
$\begingroup$

I am given an undirected, weighted graph $G$, on its base I have to create a spanning tree with such a property that the difference between the largest edge weight and the smallest edge weight is the smallest possible.

I know how to find a minimal spanning tree, e.g. using Prim's algorithm or Kruskal's algorithm, but I don't know how to find a tree satisfying the above condition. Is it enough to modify the MST algorithm in some way? Anyone have an idea how to approach this?

Improve this question
$\endgroup$
1
  • $\begingroup$ A trivial way would be guessing the weight $w$ of the edge of minimum weight in an optimal spanning tree, then built a MST on the graph induced by the edges of weight $\ge w$ (a spanning tree minimizes the weight of the maximum-weight edge). $\endgroup$
    – Steven
    May 24, 2022 at 12:21

2 Answers 2

Reset to default
4
$\begingroup$

I realized that my answer is similar to Steven's answer but maybe suitable for someone.

Based on increasing values of weights, sort the edges; e.g. $e_1,...,e_m$.

For $i=1,...,m-n+1$ (we need atleast $n-1$ edges to produce a spanning tree) produce an MST $T_i$ on $e_i,...,e_m$ and calculate the difference $d_i$ between the edge weight which is selected with maximum value and $w(e_i)$. Note that, the edge $e_i$ will be selected in produced MST, certainly.

Finally, select an MST $T_i$ with minimum $d_i$.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Does finding MST not from the whole graph but from the subgraph ${e_i,...,e_m}$ require some modification of the MST algorithm itself? I tried to implement in python your idea based on geeksforgeeks.org/… but in some cases I go out of range. It seems to me that the only thing I need to change in this function is instead of initial value $i=0$ it should be $i=k$ where $k = 0,...,n-m$ (because here we index from 0) . I know it's a bit of an implementation question but I don't know why I'm going outside the range $\endgroup$
    – PK96
    May 25, 2022 at 20:16
  • $\begingroup$ No. You should only remove the edges $e_1,...,e_{i-1}$. About going out of range, it will produce a problem if you set $k=0,...,n-m$, since $n-m$ is negative. You should set $k=0,...,m-n$. $\endgroup$
    – Majid Zohrehbandian
    May 26, 2022 at 3:14
  • $\begingroup$ Sorry, I meant $m-n$, so in theory everything should work. Thanks $\endgroup$
    – PK96
    May 26, 2022 at 5:54
  • $\begingroup$ Note that, you should check out the connectivity of the subgraph on edge set $e_i,...,e_m$, since in implementation you mentioned, it is assumed that the graph is connected. In other words, we don't have any spanning tree (and as a result an MST) on the disconnected subgraph which introduces on edge set $e_i,...,e_m$, $\endgroup$
    – Majid Zohrehbandian
    May 26, 2022 at 6:26
  • $\begingroup$ Yeah, you're right, there were cases where the algorithm didn't work when it turned out that the subgraph didn't contain all the vertices from the graph. When it finds mst only for those subgraphs that are connected the algorithm works. Thanks a lot. $\endgroup$
    – PK96
    May 26, 2022 at 9:18
4
$\begingroup$

You can solve the problem in $O(m \log n)$ time. For the sake of simplicity assume that all edge weights are distinct (this assumption can be easily removed).

Let $e_1, e_2, \dots, e_m$ be the edges in the input graph $G$ in increasing order of weight. Define $G_i$ as the subgraph of $G$ induced by $\{e_i, \dots, e_m\}$, and let $k$ be the largest integer such that $G_k$ spans $G$.

For every $i=1,\dots,k$ let $T_i$ be a MST of $G_i$ and call $M_i$ the weight of the maximum-weight edge in $T_i$. The problem is equivalent to returning a tree $T_i$ minimizing $M_i - w_i$, where $w_i$ is the weight of $e_i$ (notice that $T_i$ must include $e_i$). This is because a MST minimizes the maximum-weight of the selected edges.

As a consequence of the above discussion, we can focus on finding the trees $T_i$. We compute $T_k$ explicitly and then, for $i=k-1, k-2, \dots, 1$ we find $T_i$ by updating $T_{i+1}$ as follows:

  • Find the bottleneck edge $f_i$ in the unique path $P_i$ between the endvertices of $e_i$ in $T_{i+1}$, i.e., the edge of maximum weight in $P_i$.
  • Let $T_{i}$ be the tree obtained from $T_{i+1}$ by replacing $f$ with $e_i$.

Notice that it is possible to maintain a tree under edge insertions, deletions, and bottleneck queries in $O(\log n)$ amortized time per operation. Similarly, we can keep the maximum edge weight in $T_i$ updated in $O(\log n)$ time per iteration by storing the weights of the selected edges in a heap.

Overall the time spent is $O(m \log n)$, which also accounts for the time needed to sort the edges of $G$ and to find $T_k$.

Improve this answer
$\endgroup$
8
  • $\begingroup$ 1) This may be a silly question but I don't quite understand what this $k$ is and how determining it would work. 2) Could you explain in more detail what is: "unique path $P_i$ between the endvertices of $e_i$"? $\endgroup$
    – PK96
    May 24, 2022 at 15:07
  • $\begingroup$ And What is the $e$ to which we replace the $f$? Is it $e_i$? $\endgroup$
    – PK96
    May 24, 2022 at 15:08
  • $\begingroup$ @JohnL. Thanks! In my mind $G_k$ still contained all the vertices of $G$, but I did not define it properly. $\endgroup$
    – Steven
    May 24, 2022 at 18:02
  • $\begingroup$ @PK, $k$ essentially tells you how many of the edges $e_k, \dots, e_m$ having the largest weights you need to consider in order for them to span $G$. I only use it to ensure that $T_k$ exists. You can find it by building a maximum spanning tree of $G$ and looking at the cheapest selected edge (you can find a maximum spanning tree by using any algorithm for MST on the graph where edge weights have the opposite sign) . $\endgroup$
    – Steven
    May 24, 2022 at 18:06
  • $\begingroup$ Let $e_i = (u,v)$. $u$ and $v$ are the endvertices of the edge $e$. Given any tree (in our case $T_{i+1}$) containing $u$ and $v$, $T$ has exactly one (simple) path between $u$ and $v$. That's what $P_i$ is. To update $T_{i+1}$ after the addition of $e_i = (u,v)$ edge, you just need to remove the heaviest edge of the only cycle in $T_{i+1} + e_i$. Since we are considering edges in decreasing order of weight, this edge must lie in $P_i$. Finally, yes: the edge $e$ should have been $e_i$. $\endgroup$
    – Steven
    May 24, 2022 at 18:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.