Proof of NP-completeness of a special case of longest-path problem

Question

Problem: Longest Path

Input: An undirected graph $G=(V,E)$

Question: Is there a path of length at least $\frac{|V|}4$?

I know that in order to prove the simple version of $k$ longest path, we reduce the Hamiltonian path to longest path. How we can prove the $NP$-completeness in this special case? Should I use a reduction from Hamiltonian cycle?

Edit: A hint : Reduction from Hamiltonian path. Try to think how many vertices should be added to a special instance $G'$ of Longest path problem so that if there is a path least $\frac{|V|}{4}$ vertices in length then there is a Hamiltonian path in $G$.

Answer 1

We can prove that requiring the graph $G$ to be connected does not decrease the hardness of our problem here.

Reduce from Hamiltonian path between $2$ specified vertices, namely $s,t\in V(G)$

Like before, we want to add new vertices to the graph while keeping it connected.

Now, do some arithmetics:

A Hamiltonian path between $s$ and $t$ is of length $n-1$, where $n=|V|$

If we attach some paths of length (at most) $k$ to $s$ and $t$, then we can increase the length of a path up to $n-1+2k$.

We should have $4(n-1+2k)=|\mathcal{V}|$ in the new graph $\mathcal{G(V,E)}$.

So $|\mathcal{V}|-|V|=3n-4+8k$. Take $k=\sqrt{n}$. Alternatively, attach $s$ and then $t$ and again $s$, etc. to a new short path of length (at most) $k$ (i.e. $k$ new vertices).

The point of setting $k=\sqrt{n}$ is to prevent one from concatenating $2$ short paths attached to the same vertex (either $s$ or $t$). So, one must take one path attached to each vertex among $s$ and $t$. And the middle part of the path is a Hamiltonian path between $s$ and $t$.