GATE CS 2012 Q.29 (CS Q.29): Greedy Algorithms

Let $G$ be a weighted graph with edge weights greater than one and $G'$ be the graph constructed by squaring the weights of edges in $G$ . Let $T$ and $T'$ be the minimum spanning trees of $G$ and $G'$ , respectively, with total weights $t$ and $t'$ . Which of the following statements is TRUE?

$T' = T$ with total weight $t' = t^2$

$T' = T$ with total weight $t' < t^2$

$T' \ne T$ but total weight $t' = t^2$

None of the above

Official answer and solution

Official answer: Marks to all
From: Official GATE 2012 answer key

Why the marks went to every candidate

Official GATE answer key awarded Marks to All for this question.

Solution

Examine the properties of minimum spanning trees under monotonic transformations of edge weights.

Squaring function $f(w) = w^2$ is strictly monotonically increasing for all edge weights $w > 1$ (if $w_i < w_j$ , then $w_i^2 < w_j^2$ ).
Greedy algorithms for minimum spanning trees (such as Kruskal's or Prim's algorithm) depend purely on the relative comparison of edge weights. Because strictly monotonic transformations preserve the sorted order of edges, the minimum spanning tree of $G$ remains the minimum spanning tree of $G'$ , so $T' = T$ .
For the total weights $t = \sum_{e \in T} w_e$ and $t' = \sum_{e \in T} w_e^2$ :

By the algebraic expansion of a sum of positive terms:

t^2 = \left(\sum_{e \in T} w_e\right)^2 = \sum_{e \in T} w_e^2 + \sum_{i \ne j} w_i w_j = t' + \sum_{i \ne j} w_i w_j

For any tree with at least two edges ( $|V| \ge 3$ ), the cross terms $\sum_{i \ne j} w_i w_j > 0$ , so $t^2 > t'$ , meaning $t' < t^2$ .

Reason for Marks to All: In the degenerate case of $|V| = 2$ (a single edge tree), $t' = t^2$ . Furthermore, when graphs possess non-unique minimum spanning trees, tie-breaking might produce different tree selections. Due to these borderline ambiguities in the problem formulation, GATE awarded Marks to All.

Final answer

Marks to All (Mathematically T' = T and t' < t^2 for |V| >= 3; full credit awarded to all candidates).

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2012 Computer Science and Information Technology (CS)
Question: 29 of 65, printed as CS Q.29
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source