Question

Let \( G \) be an edge-weighted undirected graph with positive edge weights. Suppose a positive constant \( \alpha \) is added to the weight of every edge. Which ONE of the following statements is TRUE about the minimum spanning trees (MSTs) and shortest paths (SPs) in \( G \) before and after the edge weight update?

• A. Every MST remains an MST, and every SP remains an SP.
• B. MSTs need not remain MSTs, and every SP remains an SP.
• C. Every MST remains an MST, and SPs need not remain SPs.
• D. MSTs need not remain MSTs, and SPs need not remain SPs.

Hint:

In Minimum Spanning Trees (MSTs), edge weight transformations that preserve relative ordering keep the MST unchanged.

Answer 1

The Correct Option is C

When a positive constant \( \alpha \) is added to all edge weights:

• The structure of a Minimum Spanning Tree (MST) does not change:
  The structure of an MST depends on the relative order of edge weights. Since adding a constant \( \alpha \) to all edges does not affect their relative differences, the MST remains unchanged. The MST is built by considering the smallest possible edge weights, and adding the same constant to each weight does not alter their relative ranking. Therefore, every MST remains an MST.
• Shortest paths (SPs) may change:
  Shortest paths, unlike MSTs, depend on the absolute weight differences between edges. When a constant is added to every edge, it changes the total weight of all paths, potentially altering the comparison between different paths. For example, if two paths were previously equally optimal, adding the same constant to all edges could make one path less optimal compared to the other, thus altering the shortest path.

Thus, every MST remains an MST, but shortest paths need not remain shortest paths.