Question

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

I had been asked this question by my college professor while I was bunking the class.

My question is based upon Checksum, Complexity Classes & NP Complete Problems topic in portion Checksum, Complexity Classes & NP Complete Problems of Data Structures & Algorithms II

Answer 1

Correct option is (c) travelling salesman problem

Easy explanation - Hamiltonian path problem is similar to that of a travelling salesman problem since both the problem traverses all the nodes in a graph exactly once.