0
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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$.

$\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.