I\'m working on the following problem: Suppose that we\'re given a connected, un
ID: 647700 • Letter: I
Question
I'm working on the following problem: Suppose that we're given a connected, undirected graph G=(V,E) with edge weights we and a subset of vertices U?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?U must be a leaf, there must exist a vertex u?V?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?
Explanation / Answer
Hint for idea: Consider the subgraph G? induced by the vertices in V?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.