Complexity class (P/NP) variants of Hamiltonian paths problems

Question

I know that the following problems related to Hamiltonian paths in graph are NP-complete:

• Undirected Hamiltonian circuit:
  Given an undirected graph, does it has a cycle that passes through each node exactly once?
• Undirected Hamiltonian path:
  Given an undirected graph, does it has a path that passes through each node exactly once?
• Directed Hamiltonian circuit:
  Given a directed graph, does it has a directed cycle that passes through each node exactly once?

But then my textbook says following problems are NP-Hard but not NP-complete:

• Problem A: Finding a Hamiltonian circuit in a graph with number of vertices $|V|$ divisible by 3
• Problem B: Determining if Hamiltonian circuit exists in the graphs as given problem A.

Why is this so?

Answer 1

Problem A is not a decision problem. This means that by definition it is not NP-complete.

Problem B is NP-complete. But every NP-complete problem is NP-hard.

Let me remind you the definitions.

NP-complete problem. Problem P is said to be NP-complete if it is in NP and every problem in NP can be reduced in polynomial time to P.

NP-hard problem. Problem P is said to be NP-hard if every problem in NP can be reduced in polynomial time into P.