A version of the longest simple cycle problem - NP-completeness reduction proof

Question

I've been learning about proving NP-completeness via reduction, and came across the following problem:

Prove via reduction the following: whether a graph $G = (V, E)$ contains a simple cycle using $\ge \frac{1}{2}$ of the vertices is a NP-Complete problem.

The first part is to show that the above problem is in NP. That's simple enough, since a solution is verifiable in linear time by just traversing through the vertices to ensure they form a cycle, and that the no. of vertices in the solution set are $\ge \frac{1}{2}$ of the total no. of vertices.

As far as polynomial-time reduction...my thoughts so far are that you can probably reduce Hamiltonian circuit problem to it, but I'm unsure how to proceed. I suppose that, given the original graph $G$, you could first check whether the entire graph is a Hamiltonian circuit. Then if not, you could delete a random vertex from $G$ (there are a total of $|V|$ ways of doing this), and check for Hamiltonian circuit again...then if not, delete two vertices from G (there are $\binom{|V|}{ 2}$ ways of doing this), and check again for Hamiltonian circuit...and so on, all the way down to deleting $\frac{|V|}{2}$ vertices from $G$. But reducing it this way sounds cumbersome, and may even be an exponential-time reduction.

Any help would be appreciated.

Answer 1

In order to prove NP-completeness of a given problem $\Pi$, it is enough to prove that $\Pi \in$ NP and that there exists a polynomial time reduction from any NP-complete problem $\Pi^*$ to $\Pi$. The reduction must take instances of $\Pi^*$ and return instances of $\Pi$, in polynomial time, such that the answer is the same in both $\Pi^*$ and $\Pi$.

A suitable reduction from Hamiltonian Circuit has been proposed in a comment to the question: just add enough (that is $n$) isolated vertices to the graph.