Given $G=(V,E)$ undirected, connected graph and weights given by $w:E \to \mathbb R$. We also know that $|E|=|V|+87$.

Find Minimum spanning tree of $G$.

Obviously we can use Prim in $O(|V| \cdot \log |V|)$.

But can we do better by using the fact that the graph is connected, and use the sets sizes? Like removing the lightest edge from each cycle and keeping the connectivity of the graph?

  • 1
    $\begingroup$ You should consider a simpler version of the problem and attempt to generalize. What happens if $|E| = |V|$? Clearly if we add all edges, there's a cycle. What edge in that cycle should we remove to get a MST? If you figure that out you should be able to generalize it to more than multiple extra edges and come up with with at least one approach to do this in $O(c \cdot |V|)$ where $|E| = |V| + c$, or in your case $O(|V|)$. $\endgroup$ – ryan Jul 8 '17 at 20:55

The "Cycle Property" helps (If you don't know it before, try to prove it first):

Let $C$ be any cycle in $G$ and $e$ a heaviest (not necessarily unique) edge in $C$. Then there exists some MST which does not contain $e$.

You are encouraged to answer the following questions:

  • How to identify a cycle and then a heaviest edge $e$ in it?
  • What to do with the edge $e$?
  • How many times should you apply the cycle property?
  • When to stop?

Then analyze the time complexity.


Nice exercise. Here's a hint for you:

How many edges will be in the spanning tree of $G$? How many edges will be omitted?

Spend some time thinking about that, and what its implications might be.

Then, if you're still stuck, here's one more hint:

Often when thinking about MST problems, it helps to first solve the problem under the assumption that all edge weights are unique, so let's assume that. What characterizes the edges that are omitted?

  • $\begingroup$ We need to omit 88 edges to get $|E|=|V|-1$. These edges should not break the connectivity of the graph, and should have the maximum weight. So maybe we need to sort them in decreasing order and then loop through them and remove each one that doesn't break the connectivity. But it seems greedy and we might fail to get the minimum tree that way. $\endgroup$ – po1son Jul 8 '17 at 20:05

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.