Question

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

The question was asked in a national level competition.

This interesting question is from Checksum, Complexity Classes & NP Complete Problems topic in section Checksum, Complexity Classes & NP Complete Problems of Data Structures & Algorithms II

Answer 1

Right answer is (a) Hamiltonian path problem

To explain: 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.