GATE CS 1992 Q02 — Asymptotic Worst Case Time and Space Complexity

To determine which of the given problems is not $\text{NP}$-hard, let us analyze each option:

• Hamiltonian Circuit Problem: This is a classic $\text{NP}$-complete problem. Since every $\text{NP}$-complete problem is also $\text{NP}$-hard, this problem is $\text{NP}$-hard.
• 0/1 Knapsack Problem: The decision version of the $0/1$ Knapsack problem is $\text{NP}$-complete, which makes the optimization version $\text{NP}$-hard.
• Finding Bi-connected Components of a Graph: This problem can be solved in linear time $\mathcal{O}(V + E)$ using Tarjan's depth-first search (DFS) algorithm. Since it has an efficient polynomial-time algorithm, it belongs to class $\text{P}$ and is not $\text{NP}$-hard (under the standard assumption that $\text{P} \neq \text{NP}$).
• Graph Coloring Problem: Finding the chromatic number of a graph (or even deciding if a graph is $k$-colorable for $k \ge 3$) is a well-known $\text{NP}$-hard problem.

Thus, finding bi-connected components is the only problem listed that is not $\text{NP}$-hard.