Is the longest Hamiltonian cycle NP-complete?

Question

As I understand it to prove something is NP-complete you have to show that it's NP-hard by reducing and a known NP-complete problem to your problem and also prove that it is in NP which you do showing that an answer can be verified to be correct in polynomial time.

Now for the longest Hamiltonian cycle in a weighted graph, I know how the reduction would work, but I'm confused about how to verify a solution in polynomial time. To verify that the cycle is Hamiltonian is easy but how would I know if a cycle I'm looking at really is the longest?

Any help would be appreciated!

Answer 1

Usually, when we talk about the complexity of an optimisation problem (a problem where want to maximise of mininise some value, here the length of a Hamiltonian cycle), we actually look at the complexity of the decision version of that problem.

Here, the decision version is:

Does the weighted graph $G$ have a Hamiltonian path with total weight at least $x$?

For this problem, verification of the witness (=solution) is easy: we can easily check whether the solution path has weight at least $x$. So, the decision version is in NP.

---

To understand why we look at the decision version, first note that NP is a class of decision problems, so only a decision problem can be NP-complete. (although we can construct an analogue of NP for optimisation problems, as in this answer). Solving the optimisation version also solves the decision version, so the optimisation version is at least as hard as the decision version. Since the theory gets easier when working with decision problems, focusing on the decision version is often helpful.

Answer 2

Longest Hamiltonian Cycle probably isn't known to be in NP. We can certainly check in deterministic polynomial time if proposed solution is a Hamiltonian Cycle but, as you say, it doesn't seem possible to check that it's the longest one.

We usually consider the decision version of this kind of maximization problem to be, "Given an instance $X$ and a target $t$, is there a solution with value at least $t$?" So, for Longest Hamiltonian Cycle, we're given a graph $G$ and a number $t$ and we're asked if there's a Hamiltonian cycle of length at least $t$.

Clearly, Hamiltonian Cycle for unweighted graphs is reducible to this: set all the weights to $1$ and ask if there's a Hamiltonian cycle of length at least $1$ (or $n$, if you prefer).

Longest Hamiltonian Cycle is also reducible to it, though using Turing reductions rather than the many-one reductions we use for NP-completeness. We can decide LHC by binary search. Assuming all the edge weights are non-negative, we know that the longest Hamiltonian cycle must have length at least zero, and that it can't be longer than $M$, the sum of the longest edge out of each vertex. We can do binary search on the interval $[0,M]$ with $\log M$ calls to a subroutine that decides the "LHC at least $t$?" problem, and $M$ can't be more than exponential in the length of the input, so this reduction runs in polynomial time.