8.9

Idea. For every edge e = (u,v) that is not in the current minimum-spanning tree T, compare its weight w(e) with the heaviest edge on the unique path between u and v inside T. Let that heaviest-on-path edge be f and denote its weight by w(f). The exchange (cut) property of MSTs says     • if w(e) < w(f), edge e would already be in some MST,     • if w(e) = w(f), both \e and f are interchangeable,     • if w(e) > w(f), decreasing w(e) below w(f) makes e enter every MST while f leaves. Hence the least modification that changes the tree is [math]\displaystyle{\Delta_e = \max\{0,\; w(e)-w(f)\}}[/math] (plus an infinitesimal ε if the weights are real, or +1 if they are integers). The task is therefore to compute, over all non-tree edges, the minimum positive value of Δ_e and the edge that attains it.

---

Algorithm. MST-Edge-Sensitivity(G):
1. build an MST T with Kruskal   // O(m log n)
2. root T arbitrarily and pre-compute:
depth[v],          // DFS
up[v][k] – 2^k-th ancestor,
maxW[v][k] – max edge weight on path v→up[v][k]
(binary lifting table)   // O(n log n)
3. answer ← +∞; chosen ← None
4. for every edge e=(u,v)∉T with weight w:
(h, maxOnPath) ← LCA_Max(u,v)  // O(log n)
Δ ← w - maxOnPath
if Δ>0 and Δ < answer:
answer ← Δ; chosen ← e
5. return (chosen, answer)

LCA_Max(u,v): // returns (lca, maximum weight on u–v path)
if depth[u] < depth[v]: swap(u,v)
maxW = 0
// lift u to depth of v
for k = ⌊log n⌋ downto 0:
if depth[u] - 2^k ≥ depth[v]:
maxW = max(maxW, maxW[u][k])
u = up[u][k]
if u == v: return (u, maxW)
// lift both nodes
for k = ⌊log n⌋ downto 0:
if up[u][k] ≠ up[v][k]:
maxW = max(maxW, maxW[u][k], maxW[v][k])
u = up[u][k]; v = up[v][k]
// last step to lca
maxW = max(maxW, maxW[u][0], maxW[v][0])
return (up[u][0], maxW)


---

Correctness proof sketch. 1. (Cycle property) For any non-tree edge e the path in T with e forms a cycle; replacing the heaviest edge on that cycle (f) with e yields a spanning tree. 2. The tree weight changes by w(e)-w(f). It becomes smaller iff this value is negative, equal when zero, and bigger when positive. 3. Therefore the smallest positive decrease of some w(e) that flips optimality is exactly Δ_e; taking the global minimum over all non-tree edges gives the sought change. 4. The algorithm computes both f and Δ_e for every candidate, hence returns the correct minimum.

---

Complexity. Building the MST: O(m log n) Lifting tables: O(n log n) preprocessing. Path maxima for all m−(n−1) non-tree edges: O(m log n). Total: O(m log n) time and O(n log n) space – clearly polynomial. Output. Edge chosen and the minimum required modification [math]\displaystyle{\Delta = \min_{e\notin T,\, w(e)>w(f)} (w(e)-w(f))}[/math].

Back to Chapter 8