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.
I was reading: Spanning tree with chosen leaves But I think the solution is totally wrong:
- Generate an induced graph
G'
containing the verticesV'=V-U
and the edgesE'
not involving the vertices inU
- Apply Kruskal's algorithm to get
T'= MST(G')
- If
T'
does not exist then the solution does not exist - Construct an edge set
E" = (u, v)
whereu
belongs toU
andv
does not belong toU
- Apply Kruskal's algorithm on
E"
by adding edges toT'
- Return
T'
As a counter example, consider the following graph $G=(V,E)$ where: $V={1,2,3,4}, E={(1,2),(2,3),(3,4),(2,4)}$ and $U={4}$ where the weight of edges connected to 4 is -100 and 1 for the rest.
It's clear there is no MST in G where vertex 4 is leaf. But the suggested algorithm above will return a solution...