0
$\begingroup$

Definition:
A hamiltonian cycle is a cycle which crosses all of the vertices.


Problem (i): An arbitrary simple graph $G$ is given. Does $G$ have a hamiltonian cycle?


Assume that we know problem (i) is NP-Complete. How can we show that problem (ii) is NP-Complete, too?

Problem (ii): A simple graph $G$ is given. Does $G$ have a cycle of length $n/2$? ($n$ is the number of vertices)


Note 1: I know that i should use a reduction. But, The problem is that i don't know a way to translate the input of problem (ii) into an input of problem (i). Any idea?

Note 2: I want to learn a reduction. So, The thing that matters is the reduction, not just the answer of the question. I want a translation function which takes a simple graph as input and returns another simple graph which can be seen as the input of problem (i).

Thanks in advance.

$\endgroup$
1
$\begingroup$

Problem (ii) is NP-complete even for graphs with $n/2$ isolated vertices. :-)

$\endgroup$
  • $\begingroup$ Why is this true? The point of this question is to learn about reductions... Can u please provide a translation function? $\endgroup$ – Arman Malekzadeh Jun 2 '17 at 15:58
  • $\begingroup$ @ArmanMalekzade Given NP-hard problem (i), in order to show that Problem (ii) is NP-hard too, the translation function should return the input of Problem (ii), not of Problem (i). See, assume that we have an “easy” algorithm $A$ solving Problem (ii). Then we can “easily” solve Problem (i) as follows. Given a simple graph $G$ we translate it to a graph $G’$ by adding $|V(G)|$ isolated vertices and then input $G’$ to $A$. $\endgroup$ – Alex Ravsky Jun 2 '17 at 16:23
  • $\begingroup$ Then $A$ “easily” solves Problem (ii). But $G’$ has a cycle of length $|V(G’)|/2$ iff $G$ has a cycle of length $|V(G)|$, so we have constructed an algorithm which “easily” solves NP-hard Problem (i), a contradiction. $\endgroup$ – Alex Ravsky Jun 2 '17 at 16:23
  • 1
    $\begingroup$ Thanks ! That was great! $\endgroup$ – Arman Malekzadeh Jun 2 '17 at 16:24

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.