Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
