V , and a budget D.
Definition
Polynomial Certifier
Given a set of n cities and a pairwise distance function d(u, v), is there a tour of length ≤ D?
V , and a budget D.
Reduction from Hamiltonian-Cycle from simple case to general case
Given instance G = (V, E) of Hamiltonian Cycle, we create a city u′ for each node u of the graph G. We define the distance function of two different cities, u′ and v′ as follow:
Claim 4.15.4.1. Hamiltonian Cycle ≤ p Travelling Salesman Problem (This
construction of Hamiltonian Cycle leads to is a special case of Travelling
Salesman Problem)
G has Hamiltonian Cycle if and only if TSP instance has tour of length ≤ n
G has Hamiltonian Cycle ⇒ TSP instance has tour of length.
Proof. Suppose G has a Hamiltonian Cycle, then this ordering of the corresponding cities define a tour of length n. __
TSP instance has tour of length ⇒ G has Hamiltonian Cycle.
Proof. Suppose there is a tour of length at most n. The expression for the length of this tour is a sum of n terms, which implies each of which is at least 1; in this case, all equal to 1. Hence, each pair of nodes in G that correspond to consecutive cities on the tour must be connected by an edge. Thus, following the ordering of these nodes must form a Hamiltonian Cycle. __