patternMinor
Spanning tree with chosen leaves
Viewed 0 times
withleaveschosenspanningtree
Problem
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 (there
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?
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 (there
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?
Solution
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$.
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$.
Context
StackExchange Computer Science Q#40131, answer score: 4
Revisions (0)
No revisions yet.