# MST with weights in {1, 2, 3, 4, 5}

I am given an undirected connected graph with $$n$$ nodes, average degree $$\sqrt{\log n}$$, and each edge having integer weight in $$\{1,..,5\}$$. I am asked to describe MST algorithm which is as efficient as possible.

I read https://en.wikipedia.org/wiki/Minimum_spanning_tree about Dense Graph and Integer weights, but it seems that I cannot satisfy the conditions to apply the strategy for Dense graphs, and it is unclear to me what is the benefit of the integer weights.

I am thinking of simply applying Kruskal or Prim, but then I am not making use of the additional information that I have on the degree and the weights.

Any suggestion is appreciated.

Let $$G_0$$ be your input graph, label each edge $$(u,v)$$ with $$(u,v)$$ itself. Repeat the following for all values of $$i$$ from $$1$$ to $$5$$:

• Compute a spanning forest $$F_i$$ of the subgraph of $$G_{i-1}$$ induced by the edges with weight $$i$$.
• Construct the graph $$G_{i}$$ obtained from $$G_{i-1}$$ by contracting all vertices in the same connected component (i.e., tree) in $$F_i$$ into a single vertex. For each surviving edge, make sure to preserve the original label (even if one or both the original endvertices are now contracted into a new vertex).

At the end of this process, you can obtain a minimum spanning forest $$F$$ of $$G_0$$ by selecting all edges $$(u,v)$$ such that $$(u,v)$$ is a label of an edge in some $$F_i$$. If $$G_0$$ is connected then $$F$$ is also a MST of $$G_0$$.

Since each iteration can be performed in time $$O(n \sqrt{\log n})$$, the overall time complexity is also $$O(n \sqrt{\log n})$$. This is clearly optimal since $$\Omega(n \sqrt{\log n})$$ time is needed just to read the graph.

• Hmm, wow, this is a lot more involved than I tought. Thanks a lot! Mar 9, 2022 at 21:11
• @JohnL., To compute a spanning forest it is sufficient to perform any visit from an arbitrary vertex of each connected component (all edge weights are the same), so only $O(|E|)$ time is needed. Mar 9, 2022 at 22:15
• @Steven Indeed, your algorithm does not need hashtable at all assuming appropriate input format. Mar 9, 2022 at 22:23
• @IIK Or, you can sort all edges by counting sort, which takes $O(|E|)$-time. Then apply Kruskal's algorithm. The time-complexity is $O(n\sqrt{\log n}\alpha(n))$ Mar 9, 2022 at 22:24
• An easier algorithm is probably Prim's where the priority queue is implemented using $5$ buckets (one for each weight). When we need to extract the minimum, we search for the first non-empty bucket. Mar 9, 2022 at 22:41