# Improve minimum spanning tree with new edge, with better running time than O(|V|)?

The problem gives a MST $T$ and a series of $Q$ queries, each one with a new edge $e = \{u,v\}$ such that no edge between $u$ and $v$ exists in $T$. For every query, we have to improve $T$ with $e$ and print the new weight of $T$.

The best I can do is run a DFS ($O(|V|)$) to find the current path $P$ between $u$ and $v$, and find the heaviest edge $e_\text{max}$ in $P$. If $w(e) > w(e_\text{max})$, we improve $T$ removing $e_\text{max}$ and inserting $e$. The overall running time for a test case is $O(Q|V|)$.

Does anybody know an asymptotically faster algorithm for this problem?

• 1) "Faster than $O(\_)$" is an empty statement. You want to use $\Theta$. 2) What makes you think there is one? Is the one you have too slow in practice? 3) How large is $Q$? Individual queries can certainly be sped up by preprocessing (e.g., create a PQ for all node pairs and put all edges between the two in) but that will comes as a cost. 4) Note that DFS actually takes time in $\Theta(|V|)$ for you, since any given MST has $|V| - 1$ edges. Commented Aug 26, 2015 at 7:28
• I think there might be a better approach, depending on how you constructed the MST. If it was constructed with Kruskal's and the total order of the edges' weights was cached, then I think there should be an asymptotically faster approach then having to run a DFS on the graph, I'm just not exactly sure right now what the procedure would entail to guarantee an MST. Commented Aug 26, 2015 at 15:42
• @Raphael 1) Whatever. 2) Because my current solution exceeds the time limit of the online judge and certainly is not a constant factor that will save me. 3) $Q$ is large. 4) Of course I know that. 5) Do you know what competitive programming means? Training for that should really improve your algorithm skills. A red programmer on codeforces answered this question almost as if it was an easy one. But thanks for trying to help! Commented Aug 26, 2015 at 15:54
• And DFS takes time $O(|V|)$. In the best case we traverse only 2 edges, instead of $\Theta(|V|)$. Commented Aug 26, 2015 at 16:01
• @matheuscscp ad 1 + second comment: Oh, you got some lip despite not knowing how to read Landau notation. You should read this. ad 2+5: you nowhere state that you are interested in runtime in seconds, nor on what imputs, nor what the required interface is, nor what your implementation looks like. FWIW, while programming is offtopic here there may still be algorithmic improvements, but it's impossible you tell from your question what you may be doing wrong. Commented Aug 26, 2015 at 19:24

Using Heavy path decomposition.

The key idea is to partition all edges into heavy edges and light edges. Consider tree edge from parent node X to child node Y:

• heavy edge: size of sub tree Y is at least half of the size of sub tree X;
• light edge: size of sub tree Y is smaller than half of the size of sub tree X;

There are at most $O(\log |V|)$ heavy paths (path with only heavy edges) from any leaf to root. Maintaining each heavy path using segment tree or balanced BST, and converting MST into tree of heavy paths, one can query the heaviest edge $e_{max}$ between any two vertices $u$,$v$ in $O(\log |V|)$.

Another method is using Link cut tree which handles each query in $O(\log |V|)$ amortized time complexity. This can also handle the case that each query is applied to the result of previous implement.

• From the answer alone and skimming the linked articles, it's not clear to me a) how the algorithm is supposed to work and b) what it's runtime cost will be in the end. One particular concern I have is how you can assume that the edges we want to choose are all on all-heavy paths. Commented Aug 26, 2015 at 19:29
• a) "For good understander, half word suffices". b) $O(Q \lg |V|)$, of course. @Raphael, when I asked this question, I was just waiting for someone to come up with a solution that takes $O(Q \lg |V|)$ time. Although I'm a competitive programmer, it doesn't mean that I'm the best programmer. Competitive programmers are actually the best algorithmists, the whole computer science thing. And I can bet that Terence Hang is a competitor too. You should really take my advice and search about ACM ICPC, since you're a PhD student of algorithms and complexity. Commented Aug 26, 2015 at 20:06
• Explaining a): for each query, I'll use the data structure to find the heaviest edge with $O(\lg |V|)$ time, then I'll replace it if it's worth, also with $O(\lg |V|)$ time. The overall running time is $O(Q \lg |V|)$. Commented Aug 26, 2015 at 20:07
• Look, the best link about heavy light decomposition: blog.anudeep2011.com/heavy-light-decomposition Funny fact... The author is a competitor... What a coincidence... Commented Aug 26, 2015 at 20:19
• @matheuscscp a) You have not explained why any of this is correct. b) Since the inventors of these concepts are TCSists, I feel pretty comfortable ignoring unsolicited career advice, in particular if is tries to convince me that programmers are better at what I do than the people that actually excel at what I do. Commented Aug 26, 2015 at 20:52