What are common examiner traps in Minimum Spanning Trees and Shortest Paths?

Assuming shortest paths are preserved under uniform positive addition because all edge weights remain positive Failing to recognize that all spanning trees in a graph with |V| vertices always have exactly |V|-1 edges Confusing additive shifts (w(e) + c) which break shortest paths with positive multiplicative scaling (c w(e)) which preserves both MSTs and shortest paths

Minimum Spanning Trees and Shortest Paths

1 Qs · 2025 · 2 marks · 0.1 marks/paperStandard yield

Take topic test

GATE tests the fundamental invariant properties of Minimum Spanning Trees (MSTs) and Shortest Paths (SPs) under edge-weight modifications. Questions assess whether structural prope… Guide

Type

GATE CSE 2025 Set 2Q37MCQ2 marksEasyLet $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?

Topic guide

What does GATE test in Minimum Spanning Trees and Shortest Paths?

GATE tests the fundamental invariant properties of Minimum Spanning Trees (MSTs) and Shortest Paths (SPs) under edge-weight modifications. Questions assess whether structural properties—such as the fixed number of edges in any spanning tree ( $|V|-1$ ) versus variable edge counts in different path alternatives—preserve or alter optimal subgraphs when weights undergo transformations like additive shifts or scaling.

Core concepts

Fixed edge count property of Spanning Trees (|V| - 1 edges)
Variable edge/hop count across competing paths between vertex pairs
Preservation of MST under uniform addition, strictly monotonic increasing functions, or scaling
Sensitivity of shortest path algorithms (Dijkstra/Bellman-Ford) to additive shifts penalizing multi-hop paths

Recurring question patterns

Weight Transformation Invariance on MST and Shortest Paths
rare · MCQ · 2 marks · 2025
Evaluating whether optimal structures (MST, SP) remain optimal after applying uniform arithmetic operations (e.g., adding a positive constant, multiplying by a positive constant, squaring) to all edge weights.

Formulas GATE uses

Updated Weight of a Spanning Tree under Additive Shift

w^{\prime}(T) = \sum_{e \in T} (w(e) + \alpha) = w(T) + (|V| - 1)\alpha

Used to demonstrate that all spanning trees shift by the exact same constant $(|V| - 1)\alpha$ , strictly preserving relative weight rankings and MST optimality.

Updated Weight of a Path under Additive Shift

w^{\prime}(P) = \sum_{e \in P} (w(e) + \alpha) = w(P) + |E(P)|\alpha

Used to determine path length changes when different candidate paths have unequal hop counts $|E(P)|$ .

Examiner traps in Minimum Spanning Trees and Shortest Paths

Assuming shortest paths are preserved under uniform positive addition because all edge weights remain positive
Failing to recognize that all spanning trees in a graph with |V| vertices always have exactly |V|-1 edges
Confusing additive shifts (w(e) + c) which break shortest paths with positive multiplicative scaling (c w(e)) which preserves both MSTs and shortest paths

How questions are asked

Conceptual invariant checking under edge weight transformations
Statement verification / Multiple Choice selection on graph optimization properties

Paper trends

Direct conceptual MCQs focusing on structural proof-based invariants of graph algorithms without requiring extensive numerical computation.
2025

Difficulty notes

Easy questions test direct theoretical properties (e.g., additive constant preservation). Medium items introduce non-linear transformations ( $w^2, \sqrt{w}, \log w$ ) or ask for counterexample graphs. Hard items combine transformations with algorithmic behaviors (e.g., Dijkstra's greedy choice failure with negative additions or tie-breaking behaviors).