Special case of the $MST-$ Problem

Question

I am working on the following exercise:

Consider an undirected complete graph $G(V,E)$ and positive real numbers $a_1,a_2,\ldots,a_n$. The task is to find a MST with respect to the edge weights $w_e = a_ia_j$ for each $e = \{i,j\}$. Provide an algorithm that solves this problem that is as efficient as possible.

It is safe to say that just using Kruskal's or Prim's algorithm will not be sufficient here. So we should use the special structure of $w$. I came up with the following idea:

1. Sort the edges in increasing order according to their edge weights. This can be done in $\mathcal{O}(\lvert E \rvert log(\lvert E \rvert))$ time.
2. Traverse the edges, starting from the smallest and add it to $T$ if it contains an unvisited vertex. Mark the newely visited vertices. This can be done in $\mathcal{O}(\lvert E \rvert)$ time.

But this algorithm is not as efficient as possible for it has $\mathcal{O}(\lvert E \rvert log(\lvert E \rvert))$ time complexity. The problem here is the procedure in step 1. Could we somehow leave it out?

Answer 1

Since the graph is complete, you can connect each vertex with any other vertex. Note that each vertex must be connected to the tree and hence has an incident edge in the tree.

Assuming all weights are positive, choose a vertex $v$ with the minimum weight and construct the tree from all incident edges with this vertex. The tree is hence a star graph with $v$ the center of the star.

Assuming the numbers can be negative (which is not specified in you question), then distinct two cases. the first one, all weights are negative. Hence, it turns into the case above, since all products have to be positive.

The second case is where we have at least one negative weight and one positive weight. Let $u$ be a vertex with the maximum positive weight. Let $v$ be a vertex with negative weight with maximum absolute value among all negative weights. connect $u$ to all vertices with negative weights and $v$ to all vertices with positive weights. Be aware of not adding the edge between $u$ and $v$ twice.

Try to proof the correctness as an exercise. It should be clear using elementary math and an exchange argument.