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 Gateway to Computer Science Excellence

+11 votes

Best answer

- Is NPC and hence NP hard.
- 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
- Is in P. See the algorithm here based on DFS: http://en.wikipedia.org/wiki/Biconnected_component
- NPC and hence NP hard.

Correct Answer: $C$

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

0

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.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,394 answers

198,594 comments

105,445 users