0
$\begingroup$

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

Improve this question
$\endgroup$
2
  • 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, 2022 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, 2022 at 18:16

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.