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

Question

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.

Answer 1

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.