0
$\begingroup$

Given a graph G = (V, E) with edge lengths c : E → R, and a number d ∈ R, is there a Hamilton cycle of length l ≤ d in G? Show that the Travelling-Salesman problem is contained in the complexity class NP.

I am somewhat struggling with this exercise because I have little problem understanding the formality. I know that we need to show that there is a polynomial algorithm which verifies a given solution which we refer to as "certificate". But what exactly is the certificate here? Is it a given path (which would be easy to verify since you only have to check whether the nodes are adjacent and the costs are ≤ d) or is it just d and we have to check whether there exists a path ≤ d? But the latter is not verifiable in polynomial time as it is requires n!.

$\endgroup$

2 Answers 2

1
$\begingroup$

TSP can be expressed as a decision problem and an optimisation problem.

Here, as you said, a solution to the optimisation problem can be seen as a certificate to the decision problem: if you are given a certain path in $G$, you can verify in polynomial time that:

  1. it is a Hamiltonian cycle;
  2. its weight is lesser or equal to $d$.

That's enough to prove that TSP $\in\mathsf{NP}$.

$\endgroup$
1
$\begingroup$

Definition of an NP problem: An NP problem is a decision problem, which means for every instance there is an answer, either “Yes” or No”. For each yes-instance there is a polynomial size correct certificate. And there is a program which given an instance and a certificate will tell you in polynomial time “Yes” if given a yes-instance and a correct certificate, and “don’t know” if it is a yes-instance with an incorrect certificate, or a no-instance.

It’s up to the person trying to prove that a problem is in NP to define what the certificate would be. For example for the travelling salesman decision problem the order in which to visit nodes seems a good choice for a certificate.

(What would be an incorrect certificate? For example an order to visit nodes in, with total distance more than required).

For TSP, the problem is “is there a tour with length <= K”. The similar problem “Does the shortest tour have length exactly K” will have problems defining and finding a certificate.

$\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.