3,428 views

Which of the following problems is not $\text{NP}$-hard?

1. Hamiltonian circuit problem
2. The $0/1$ Knapsack problem
3. Finding bi-connected components of a graph
4. The graph coloring problem

### Subscribe to GO Classes for GATE CSE 2022

1. Is NPC and hence NP hard.
2. Is again NP hard (optimization version is NP hard and decision version is NPC). Ref: http://stackoverflow.com/questions/3907545/how-to-understand-the-knapsack-problem-is-np-complete
3. Is in P. See the algorithm here based on DFS: http://en.wikipedia.org/wiki/Biconnected_component
4. NPC and hence NP hard.

Correct Answer: $C$

by

It is in P.

A: NPC. Hence, NPH.

B: NPH.

D: NPC. Hence, NPH.

Assuming that you know all the terminologies of the question, here are the answers:

Let V are the number of VERTICES and E are number of EDGES.

A:  Time complexity of Hamiltonian circuit is O( $n^{2}2^{n}$) where n is number of vertices. Hence, NPH.

The Hamilton circuit problem is polynomial time reducible to 3-SAT.
Now, since 3-SAT is NP complete therefore, Hamilton circuit problem also become np complete. Means NP hard.

B:  Time complexity of 0/1 Knapsack is O(nW) where W is size of knapsack.

While the decision problem is NP-complete, the optimization problem is NP-hard, its resolution is at least as difficult as the decision problem, and there is no known polynomial algorithm which can tell, given a solution, whether it is optimal (which would mean that there is no solution with a larger V, thus solving the NP-complete decision problem).

D: Time complexity of Graph coloring is O$(V^{2}+E)$

This is NP-Complete. Reason : https://math.stackexchange.com/questions/125136/how-is-the-graph-coloring-problem-np-complete

C: Time Complexity of finding bi-connected components of a graph is O$(V+E)$. It is straightforward P time taking complexity.

@Akash Papnai

Time complexity of Hamiltonian circuit is O( n22nn22n) where n is number of vertices. Hence, NPH.

This is a statement not an explanation. Please explain the reason for it.

The Hamilton circuit problem is polynomial time reducible to 3-SAT.

Now, since 3-SAT is NP complete therefore, Hamilton circuit problem also become np complete. Means NP hard.
There is a subtle change. You should reduce a known NP-complete problem to the current problem and show that the current problem is in NP for showing it as NP-complete.

The statement should be rephrased to “The 3-SAT problem is reducible to Hamiltonian Circuit problem in polynomial time”