Increasing an edge weight. Shortest time to recompute an $MST$?
If you're required to solve this &quot;one-shot&quot; 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$.