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?

  • $\begingroup$ See what happens if you make a forest with the lightest edge incident on each element of $U$. $\endgroup$
    – Louis
    Mar 6 '15 at 12:32
  • $\begingroup$ is there a version of this where G is acyclic? $\endgroup$ May 2 '21 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$.

  • $\begingroup$ That's not a full answer, but a hint that gets you to within a µ from one. $\endgroup$
    – Raphael
    Mar 6 '15 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'
  • $\begingroup$ @D.W. I have updated the answer. Hope it helps! $\endgroup$
    – Stuxen
    Nov 1 '19 at 23:36

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.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.