0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.