748 views

Choose the correct alternatives (more than one may be correct) and write the corresponding letters only:

Which of the following problems is not $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
edited | 748 views

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.
edited by

It is in P.

A: NPC. Hence, NPH.

B: NPH.

D: NPC. Hence, NPH.