1
$\begingroup$

I am working on the following exercise:

Consider an undirected graph $G = (V,E)$. Let $T^* = (V,E_{T^*})$ be a $MST$ and let $e$ be an edge in $E_{T^*}$. We define the set of all values that can be assigned to $w_e$ such that $T^*$ remains a MST as $I_e$.

  1. Show that $I_e$ is an interval.
  2. Devise an efficient algorithm to calculate $I_e$ for a given edge $e$.
  3. Devise an efficient algorithm that determines all $I_e$ in one step. It should be more efficient than repeatedly using the algorithm from 2.

I did the following:

  1. Consider an edge $e$ in $E_{T^*}$. Delete it from $G$ and find the new lowest weighted edge connecting the resulting components, say $e'$. The upper bound for $I_e$ is $w(e')$. The lower bound would be $-\infty$.
  2. Use the algorithm sketched in 1.
  3. I do not know what to do here. Could you help me?
$\endgroup$

1 Answer 1

1
$\begingroup$

The solution in short. For each edge $e$ not in the tree, check the path between its endpoints in the tree. The weight of each edge on this path is upper-bounded buy the weight of $e$. Keep track of the smallest upper-bound for each edge on the tree while iterating over all edges not in the tree. Following is a sketch of the correctness.

Let us call an edge in a simple cycle Heavy for this cycle, if its weight is maximum among all edges in the cycle. We claim that each edge $e$ in $G\setminus T^*$ is Cycle heavy for some cycle in $G$.

Proof. By adding the edge $e$ to the tree, it constructs a cycle with a path in the tree between its endpoints. If there is an edge in the cycle with strictly heavier weight, we can remove this edge and keep $e$ constricting a lighter tree which contradicts the assumption that the given tree is minimum.

On the other hand, it is not hard to prove that an edge is in an MST of a given graph if it is not heavy for any simple cycle containing this edge. The correctness of the sketched algorithm follows directly from this statement.

$\endgroup$

Your Answer

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

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