# 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 (there 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$. Mar 6, 2015 at 12:32
• is there a version of this where G is acyclic? May 2, 2021 at 3:54

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. Mar 6, 2015 at 17:48

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'

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.