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

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.

• I'm not sure what specifically you are asking. Can you edit your post to ask a more specific question? "Any help?" is pretty vague. Open-ended questions aren't a good fit here -- see our help center. Are you asking us to solve the problem for you and show you a reduction? Are you asking us to check whether your proof is correct? Are you asking us to offer suggestions on how to improve your proof? – D.W. Jul 13 '16 at 17:19

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.