# Spanning tree with chosen leaves

I'm working on the following problem:

Suppose that we're given a connected, undirected graph $G = (V, E)$ with edge weights $w_e$ and a subset of vertices $U \subset V$. We want to find the lightest spanning tree in which the nodes of $U$ are leaves (they may be other leaves as well). We want to do so in $O(|E|\log(|V|))$ time.

Here's my thinking: since every node $v \in U$ must be a leaf, there must exist a vertex $u \in V \setminus U$ that is the source (i.e. each leaf in $U$ is connected to $u$). However, I'm having trouble find a way to do this that doesn't involve running a polynomial time algorithm. Can anyone help?

• See what happens if you make a forest with the lightest edge incident on each element of $U$. – Louis Mar 6 '15 at 12:32

Hint for idea: Consider the subgraph $G'$ induced by the vertices in $V \setminus U$. Compute its MST $T'$. Then how should you attach the vertices in $U$ to $T'$?

Hint for implementation: To achieve $O(|E| \log |V|)$, you still run ordinary MST on the original graph $G$, but pay special attention to the vertices in $U$.

• That's not a full answer, but a hint that gets you to within a µ from one. – Raphael Mar 6 '15 at 17:48

I guess a few modification to the graph may close to the answer. The set $U$ must be chosen and they must form the leaves, right? suppose $u \in U$, For every $v$ adjacent to the $u$ find the minimum edge $\{u,v\}$, assign weight $0$ to it and then remove every other edge connected to the $u$. In the result graph every vertex $u \in U$ necessarily form the leaves.

But you must be careful that every two vertices belong to $U$ must be either disconnected or be on at least one cycle in order to form leaves.

The solution can be found here which is similar to that suggested by @hengxin

Minimum spanning tree with chosen leaves

Outline of the algorithm

1. Generate an induced graph G' containing the vertices V'=V-U and the edges E' not involving the vertices in U
2. Apply Kruskal's algorithm to get T'= MST(G')
3. If T' does not exist then the solution does not exist
4. Construct an edge set E" = (u, v) where u belongs to U and v does not belong to U
5. Apply Kruskal's algorithm on E" by adding edges to T'
6. Return T'
• @D.W. I have updated the answer. Hope it helps! – Deep Bodra Nov 1 at 23:36