0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – D.W. Jul 13 '16 at 17:19
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ It seems you created multiple accounts. See here for how to fix that. $\endgroup$ – Raphael Jul 13 '16 at 12:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.