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:

  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'

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...

  • 1
    $\begingroup$ OK. Do you have a question? What is your question? We are a question-and-answer site, so we require you to articulate a specific question. $\endgroup$
    – D.W.
    May 13 at 7:32
  • $\begingroup$ Hello, unregistered user! You are wrong. If you register an account, I will tell you why. $\endgroup$
    – John L.
    May 13 at 18:16


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.