dang_252's blog

[Help] Proof for a problem about Maximum Spanning Tree
By dang_252, history, 4 years ago, In English

Recently I came across a problem:

Given an undirected graph $$$n$$$ vertices with $$$m$$$ weighted edges. Find a simple cycle with the value "Max weighted edge" + "Min weighted edge" maximized and print that value.

So my algorithm is:

  • Build a Maximum Spanning Tree

  • With an edge $$$u-v$$$ weight $$$w$$$ that is not in the MST, take max answer $$$w$$$ + Max weighted edge on that path $$$u-v$$$ on the MST.

In the second point, I could not prove if "Max weighted edge on that path $$$u-v$$$ on the MST" is maximized. What if there is another path from $$$u$$$ to $$$v$$$ with "Max weighted edge" larger.

I tried to prove that the Maximum Spanning Tree guarantees that the path $$$u-v$$$ have "max weighted edge" maximized but it turned out quite wrong in my mind as we can use edges that is not belong to the current MaxST to lead $$$u$$$ to a large edge then lead to $$$v$$$.

So how my algorithm actually guarantees with an edge $$$u-v$$$ weight $$$w$$$ that is not in the MST, the "Max weighted edge on that path $$$u-v$$$ on the MST" is the maximum "Max weight edge" path from $$$u$$$ to $$$v$$$?

How to prove that from $$$u$$$ to $$$v$$$ there is not any other path that have "Max weighted edge" larger than the one in the MST which will make the answer better?

Thanks in advanced.

  • Vote: I like it
  • +29
  • Vote: I do not like it

»
4 years ago, # |
← Rev. 2   Vote: I like it +9 Vote: I do not like it

If there would be a larger edge on the path from $$$u$$$ to $$$v$$$, then the maximum spanning tree algorithm would naturally replaced that edge with the smallest edge on the path.

When the smallest on the path from $$$u$$$ to $$$v$$$ be discarded, the tree would be separated into two components.

Also adding the larger edge would merge those two components.

Since the order of iteration of the edges while adding to the maximum spanning tree is from the largest to the smallest, rather than the smaller edge, the larger edge would be priorly considered to be added to the maximum spanning tree.

As mentioned, since the larger edge merges those two components too, it would be added to the maximum spanning tree.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    Consider this graph:

    Screenshot-2020-10-30-183245.png

    We have the MaxST will be:

    1 4 3

    2 4 4

    2 3 5

    But if we go by the path $$$1 \rightarrow 3 \rightarrow 2$$$ which will have max weight ($$$5$$$) larger than using the edges on the MaxST : $$$1 \rightarrow 4 \rightarrow 2$$$ for path $$$1 \rightarrow 2$$$

    So if your point is to prove that there can't be larger max edge path by not using edges on the MaxST then this example was the counter for that.

    If I misread your comment or something, pls fix me. Thanks

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      I think your counterexample is right and my comment proves that the maximum spanning tree maximizes the smallest edge on the path from $$$u$$$ to $$$v$$$.

      Sorry for misunderstanding.

      → Reply
»
4 years ago, # |
  Vote: I like it +28 Vote: I do not like it

Indeed, path in max spanning tree doesn't maximize maximum edge on paths.

However it does maximize minimum edge on path. It's obvious that spanning tree built with kruskal's satisfies this property. To prove for any mst consider a path from u to v which is has strictly better than the one in mst. Remove min edge from u->v path in mst the graph still stays connected because the other path only uses edges >min adding one(not any, but 1 is enough since tree will have 2 connected components and the graph is still connected) of the edges from the other path will make this graph connected and this edge will be strictly larger the one we removed. Therefore our st wasn't mst, a contradition. (This proof doesn't work for max edge because we can't guarantee that mst will have greater cost after doing this)

I believe you can consider back edges used(edges / mst edges) in the path and conclude that it's optimal to use only one through tedious casework. Here's a simpler method. Let's consider this "naive" algorithm: Fix max edge (u, v) and greedily find a path from u to v which maximizes minimum edge weight on path and doesn't use that edge. Using the above property you can see that it's the same as maximizing weight(u, v) + cost of u->v path in MST of Graph / (u, v) edge. Turns out this spanning tree can be obtained by doing this: remove (u, v) and add the cheapest edge which will make the graph connected. 1 operation is enough because if we do 2+ at least one operation clearly doesn't involve (u, v) so if it's good then it would also mean that our current st is not mst. It's not hard to see that your algo is a smart way of considering all the possible operations.

It turned out to be much messier than I expected. Should've used proof by intimidation.

→ Reply