# Find MST after decrease weight of some edges

We are given an undirected weighted graph $$G=(V,E)$$ that contains at most $$2n$$ edges, as well as an MST of $$G$$.

If we decrease the weight of exactly $$n$$ edges, is it possible to compute an MST of $$G$$ in $$O(n)$$?

If it's not possible, are there any lower bound that show us, it can't be done in linear time?

Suppose that you could solve your problem in time $$T(n)$$.

Given an arbitrary weighted graph on $$n$$ vertices and $$m \leq 2n$$ edges, replace all weights by some large weight $$M$$ which is larger than all weights in the original graph. Find a spanning tree for the new graph in linear time (using BFS/DFS); since all weights are the same, this is also an MST. Now apply your procedure twice to find an MST for the original graph, in time $$O(T(n))$$.

Therefore your problem isn't easier than finding an MST for a graph with $$n$$ vertices and at most $$2n$$ edges, which is not expected to be solvable in linear time. However, no nontrivial lower bounds are known, to the best of my knowledge.