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.

• D.W.: 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?

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.

• Raphael: It seems you created multiple accounts. See here for how to fix that.