1
$\begingroup$

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?

$\endgroup$
0

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.