TIFR CSE 2024 | Part B | Question: 13

Question

Suppose we are given a graph $\text{G=(V, E)}$ with non-negative edge weights $\left\{w_{e}\right\}_{e \in E}$.

Consider the following problems:

P1: Finding a minimum spanning tree of $\text{G}$.
P2: Finding a maximum spanning tree of $\text{G}$.
P3: Finding a cycle of smallest weight in $\text{G}$.
P4: Finding a cycle of largest weight in $\text{G}$.

Note: a cycle consists of distinct vertices.

Assuming $\mathrm{P} \neq \mathrm{NP}$, which of the above problems can be solved in polynomial time?

• A. $\text{P1, P2 but not P3, P4}$.
• B. $\text{P1, P3 but not P2, P4}$.
• C. $\text{P1 but not P2,P3, P4}$.
• D. $\text{P1,P2,P3 but not P4}$.
• E. $\text{P1, P4 but not P2, P3}$.