# The existance of a cycle of length $n/2$ in a simple graph is NP-Complete

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).

Problem (ii) is NP-complete even for graphs with $n/2$ isolated vertices. :-)
• @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$. – Alex Ravsky Jun 2 '17 at 16:23
• 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. – Alex Ravsky Jun 2 '17 at 16:23