# Hamiltonian Path Problem Multiple choice Questions and Answers (MCQs)

## Click on any option to know the CORRECT ANSWERS

 Question 1
Which of the following algorithm can be used to solve the Hamiltonian path problem efficiently?
 A branch and bound B iterative improvement C divide and conquer D greedy algorithm

Question 1 Explanation:
The Hamiltonian path problem can be solved efficiently using branch and bound approach. It can also be solved using a backtracking approach.

 Question 2
The problem of finding a path in a graph that visits every vertex exactly once is called?
 A Hamiltonian path problem B Hamiltonian cycle problem C Subset sum problem D Turnpike reconstruction problem

Question 2 Explanation:
Hamiltonian path problem is a problem of finding a path in a graph that visits every node exactly once whereas Hamiltonian cycle problem is finding a cycle in a graph.

 Question 3
Hamiltonian path problem is .....
 A NP problem B N class problem C P class problem D NP complete problem

Question 3 Explanation:
Hamiltonian path problem is found to be NP complete. Hamiltonian cycle problem is also an NP- complete problem.

 Question 4
There is no existing relationship between a Hamiltonian path problem and Hamiltonian circuit problem.
 A true B false

Question 4 Explanation:
There is a relationship between Hamiltonian path problem and Hamiltonian circuit problem. The Hamiltonian path in graph G is equal to Hamiltonian cycle in graph H under certain conditions.

 Question 5
Which of the following problems is similar to that of a Hamiltonian path problem?
 A knapsack problem B closest pair problem C travelling salesman problem D assignment problem