2
$\begingroup$

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?

$\endgroup$
  • $\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
2
$\begingroup$

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

$\endgroup$
  • $\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
0
$\begingroup$

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.

$\endgroup$

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.