0
$\begingroup$

In [1], Corollary 2.3, after proving that HC-k-(n-even) for a fixed k >= 3, the paper says that HC-k-regular being NP Complete is an inmediate consequence of the former.

Where: HC-k-regular-(n-even) means if the graph has a hamiltonian cycle in a k-regular graph with an even number of nodes.

And HC-k-regular means the graph has a hamiltonian cycle in a k-regular graph.

I don't understand how or why "HC-k-regular-(n-even) is NP Complete" implies "HC-k-regular is NP Complete". Why graphs with odd number of nodes are not considered in an explicit way?

[1] Complexity of the hamiltonian cycle in regular graph problem

Improve this question
$\endgroup$
1
  • $\begingroup$ inmediate -> immediate? $\endgroup$
    – greybeard
    Commented Sep 15, 2022 at 8:17

1 Answer 1

Reset to default
2
$\begingroup$

Hmmm, I think by definition "HC-k-regular-(n-even) is NP-Complete" implies "HC-k-regular is NP-hard", since every NP problem can be reduce to an instance of HC-k-regular-(n-even) problem, which is also a HC-k-regular instance. Together with the obvious result that "HC-k-regular is NP", we can get the conclusion "HC-k-regular is NP-Complete". More intuitively, it's something like "${\sf SAT} \cup 0^n$ is NP-Complete".

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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