How can the time complexity be achieved?

[evinda]

Hello! (Wave)

It is given as input an undirected graph $G=(V,E)$, weights of edges $w_e$ and a subset $U$ of the vertices.

The output should be the minimum spanning tree at which the vertices of the set $U$ are leaves.
(The tree could also have leaves from the nodes of the set $V-U$).

I want to run an algorithm for the above problem that runs in time $O(|E| \cdot \log|V|)$.

So we couldn't apply Borůvka's algorithm or Prim's algorithm, because we would have to call them $|V|$ times.. Or am I wrong?

If it is like that, what else could we do? (Thinking)

 

[Future Bruno]

One approach could be to use Kruskal's algorithm with a modification. We can first sort the edges in non-decreasing order of their weights. Then we can iterate through the edges, and add them to the spanning tree only if it does not create a cycle, or if it includes at least one vertex from the set $U$. This way, we can ensure that all the vertices in $U$ are leaves in the minimum spanning tree. Since the sorting of the edges takes time $O(|E|\log |E|)$, and the loop over the edges takes time $O(|E|)$, the total running time of this algorithm is $O(|E| \log |E| + |E|)$ which is equivalent to $O(|E| \log |V|)$.