NP-completeness proofs (2): Hamiltonian path, cycle, and Travelling Salesman Problem

17 Dec, 2024

This post gives you the proofs of three classical NP-complete problems—Hamiltonian path, Hamiltonian cycle, and Travelling Salesman Problem (TSP).

Note. The Hamiltonian cycle problem is a special case of TSP, where distance between two cities are set to 0 if they are adjacent and 1 otherwise, and the total distance are bounded by $|V|$. These two problems are way too close in this regard. Therefore, if you want to prove the NP-completeness of TSP on an exam, I recommend reducing from the Hamiltonian path problem (or using a two-step proof by TSP ≥ HC ≥ HP) to ensure full grades.

Definitions

Definitions.

Hamiltonian cycle decision problem: Given a graph $G(V,E)$, does there exist a cycle $C$ that visits each vertex exactly once?

Hamiltonian path decision problem: Given a graph $G(V,E)$, does there exist a path $P$ that visits each vertex exactly once?

Travelling Salesman decision problem: Given a list of cities and the distances between each pair of cities, does there exist a route of length at most $L$ that visits each city exactly once and returns to the origin city?

Proofs

P1: Hamiltonian cycle

Proof by reduction from Hamiltonian path.

1. Certificate: Verifying the cycle visits all vertices, costing $O(|V|)$, which is in polytime. Thus the problem is NP.

2. Reduction: Construct a new graph $G^{\prime }$ by create a new vertex $s$ that connects all vertices in $G$. If we can find a Hamiltonian cycle in $G^{\prime }$, it gives us a Hamiltonian path in $G$.

   

3. Construction from iterating all vertices costs $O(|V|)$, which is in polytime. In conclusion, the Hamiltonian cycle problem is NP-complete.

P2: Hamiltonian path

Proof by reduction from Hamiltonian cycle.

1. Certificate: Verifying the path visits all vertices, costing $O(|V|)$, which is in polytime. Thus the problem is NP.

2. Reduction: Let $u$ be a vertex in $V$. Create a new vertex $u^{\prime }$ that mirrors all edges connected to $u$. Create a new vertex $s$ that connects $u$, and a new vertex $t$ that connects $u^{\prime }$.

   

   If a given algorithm finds a Hamiltonian path in the new graph $G^{\prime }$, it must start with $s$ and ends with $t$ since both only have 1 degree. Then the original $G$ must have a Hamiltonian cycle that starts and ends with $u$.

   By iterating through all possible $u\in V$, this construction can use the solution of Hamiltonian path to deduce Hamiltonian cycle.

3. The construction is at most $O(|E|)$ if all edges are directly connected to $u$. Iterating all possible breakpoints $u$ would make the total reduction $O(|V|\cdot |E|)$, which is still in polytime. In conclusion, the Hamiltonian path decision problem is NP-complete.

P3: Travelling Salesman Problem

Proof by reduction from Hamiltonian cycle.

1. Certificate: Verifying the route visits all cities, costing $O(L)$, which is in polytime. Thus the problem is NP.

2. Reduction: Given a graph $G(V,E)$ in Hamiltonian cycle problem, we can construct a new graph $G^{\prime }(V,E^{\prime })$ in TSP, where $E^{\prime }=\{(u,v)\mid u,v\in V\}$. The distances between cities is then defined as

   $w(u,v)=\{\begin{array}{cc}0,\hfill & \text{if}(u,v)\in E,\hfill \\ 1,\hfill & \text{otherwise.}\hfill \end{array}$

   Given an algorithm to find a solution of TSP with $L=0$, we can directly get the solution to the Hamiltonian cycle.

3. Construction of $G^{\prime }$ costs $O(|V{|}^2)$ for iteration of all vertex pairs, which is in polytime. In conclusion, the TSP is NP-complete.

#Algorithms #Math notes