The Gateway to Computer Science Excellence
+5 votes
1.1k 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
in Algorithms by Veteran (52.2k points)
edited by | 1.1k views

3 Answers

+11 votes
Best answer
  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 Veteran (431k points)
edited by
+2 votes
Answer: C

It is in P.

A: NPC. Hence, NPH.

B: NPH.

D: NPC. Hence, NPH.
by Boss (33.9k points)
0 votes

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).

Source: https://en.wikipedia.org/wiki/Knapsack_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.

 

Hence C is the answer.

by Junior (841 points)
edited by
0

@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.

0
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.
0
Mention this in the answer.
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,309 answers
198,337 comments
105,024 users