# Increasing an edge weight. Shortest time to recompute an $MST$?

I have an $$MST$$ tree $$T$$. I increase the weight of a single edge $$e$$ by $$c$$(a non negative constant).

I need to recompute an $$MST$$ as fast as i can. How I do this? The idea I had in mimd is to remove $$e$$ from $$T$$. Loop over all crossing edges between the two "halves" of $$T$$. See which one is minimal weight. Add her instead.

This will require $$O(|E|)$$ time. Is there a faster idea? Or does my idea requires less than $$O(|E|)$$?

I suspect a more efficient algorothm exists because i do not use the fact that $$e$$'s weight increased.

## 1 Answer

If you're required to solve this "one-shot" problem, you're not allowed to perform any pre-processing, and you don't have any additional assumption, then a running time of $$O(m)$$ is the best you can hope for.

Indeed, consider an edge $$e$$ such that the fundamental cut $$C_e$$ induced by $$e$$ contains $$\Theta(m)$$ edges. All edges in $$C_e$$ have distinct weights that are strictly larger than the weight $$w_e$$ of $$e$$. For every value of $$m$$, it is easy to come up with a graph $$G$$ , an associated MST $$T$$, and and edge $$e$$ that satisfy these properties.

Suppose that there is a (deterministic) algorithm $$A$$ with a running time of $$o(m)$$. Then, when $$A$$ is run with inputs $$G$$, $$T$$, and $$e$$ there is at least one edge $$f \in C_e$$ whose weight is never read by $$A$$, and such that $$f$$ is not added to the new MST $$T'$$.

We can then run $$A$$ with inputs $$G'$$, $$T$$, and $$e$$, where $$G'$$ is a copy of $$G$$ in which the weight of edge $$f$$ has been set to $$w_e$$. The returned MST must still be $$T'$$, but this is incorrect since the new MST must include edge $$f$$.