Approximation of Hamiltonian cycles

Question

Let's define the $\texttt{MinHalfSimpCycle}$ search problem: Given $G=(V, E)$ a complete, undirected graph with weights on the edges. We want a simple cycle in $G$ (each vertex appears in it at most once) of length $\bigl\lfloor|V|/2 \bigr\rfloor$, with minimal weight (the sum of the weights on the edges of the cycle).

Also, we will define $$\texttt{Hamiltonian}_{\texttt{st}}=\left\{\langle G, s, t\rangle: \text{There is a simple path from $s$ to $t$ passing through all vertices in $G$}\right\}.$$ Here $G$ is an undirected graph.

Reminder: We know that the following language is $\mathbf{NP}$-complete: $$\texttt{Hamiltonian}_{\texttt{cycle}}=\left\{\langle G \rangle: \text{There is a simple cycle passing through all vertices in $G$}\right\}.$$ Here $G$ is an also undirected graph.

I am interested to prove that if there is a polynomial algorithm that $\rho$-approximates the $\texttt{MinHalfSimpCycle}$ search problem for a constant $\rho>1$, then $\mathbf{P=NP}.$

Answer 1

Claim. For every $\rho \geq 1$, there is no polynomial $\rho$-approximation algorithm for $\texttt{MinHalfSimpCycle}$, unless P=NP.

Proof. Let $G$ be an instance of the Travelling Salesman Problem (TSP). That is, $G$ is an edge-weighted complete graph, and the goal is to find a Hamiltonian cycle in $G$ of minimum cost. Let $G'$ be obtained from $G$ by adding a new vertex $v'$ for each $v \in V(G)$ and edge $v'v$ with weight $1$ (the weight of $vv'$ is actually not important). Every cycle in $G'$ using exactly half the vertices of $G'$ is a Hamiltonian cycle of $G$. Therefore, if there is a polynomial $\rho$-approximation algorithm for $\texttt{MinHalfSimpCycle}$, then there is a polynomial $\rho$-approximation algorithm for TSP. However, it is well-known that this would imply P=NP.