1
$\begingroup$

I'm working on understanding graphs and graph algorithms.

The problem is from: https://courses.engr.illinois.edu/cs374/fa2020/labs/sol/lab_12_b_sol.pdf (Q 1.D)

Describe an efficient algorithm to update the minimum spanning tree $T$ of a weighted undirected graph G when the weight of one edge $e \notin T$ is decreased.

I understand the solution and it makes sense to me intuitively that we add in that edge e to T, so $T'=T+e$ then that would make a cycle which we would just go through all the edges in the cycle and remove the one with the highest weight. This is clearly right because it's the only weight that was changed so the other choices we made about other vertices not in the cycle remain unchanged, adding e and removing the other max weight edge would then give a MST intuitively.

What I don't understand is how would I prove this algorithm still results in an MST rigorously?

I feel like since it seems obvious to me, I'm not seeing the rigorous way of explaining it. I only have the hand-wavy 'it's right because it's obviously right' explanation above which I realize is not an actual proof at all.

$\endgroup$
4
  • $\begingroup$ Are you familiar with the cut property? $\endgroup$
    – Pål GD
    Commented Nov 18, 2022 at 23:22
  • 1
    $\begingroup$ Yes, in this case though because we're removing the highest weight edge to get the components of the cut and then adding the lowest weight. This seems like it's the opposite of the cut property so I'm not sure how to use the property in the proof. $\endgroup$
    – DarkCave
    Commented Nov 18, 2022 at 23:28
  • $\begingroup$ @PålGD It would be great if you can answer using the cut property. $\endgroup$ Commented Feb 28 at 18:20
  • 1
    $\begingroup$ @KennethKho done $\endgroup$
    – Pål GD
    Commented Mar 3 at 18:48

2 Answers 2

2
$\begingroup$

Let $T$ be the original spanning tree, and let $uv$ be the modified edge. Let $xy$ be a heaviest edge on the unique $u$-$v$-path in $T$.

Remove $xy$ from $T$ to obtain $T'$, two disconnected trees consisting of connected components $A$ and $B$. Clearly, $A$ and $B$ are minimum spanning trees of their respective sets of vertices. By the cut property, a minimum weight edge with one endpoint in $A$ and one endpoint in $B$ will be in an MST.

Hence, if $uv$ is now of a lower weight than $xy$ we add $uv$ otherwise we keep $T$ as it was.

$\endgroup$
-1
$\begingroup$

Think of the vertices of $G$ to be partitioned into two sets : $V_1$ and $V_2$, where $V_1$ consists of the vertices in the cycle and $V_2$ are the remaining vertices. Now In the graph, $G\setminus V_1$, the MST is what you had before, nothing has changed since $G\setminus V_1$ has not changed. In $G\setminus V_2$, you found the MST by the cycle argument.

Now MST of the two graphs combined, consists of the union of the MST of them and a single edge connecting these two MSTs. Convince yourself, that this hasn't changed and that should complete the proof.

$\endgroup$
1
  • 1
    $\begingroup$ This proves that you obtain the MST of the two MST's and the edge that joins them. But it does not prove that it is an MST of the initial graph. $\endgroup$
    – user16034
    Commented Dec 19, 2022 at 16:54

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.