Given N positive integers are they the integers 1-N : What is the relationship between this problem and NP?
Recognizing that a path is a Hamiltonian path is easy. Finding one in the first place may be hard (the number of candidates is large).
The defining property of problems in NP is that verifying a solution is &quot;easy&quot; (in P). Your problem is one part of verifying a solution of a Hamiltonian path problem. (You also have to verify that the path is a subgraph of the input graph.)